./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje --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 82b98e74657ce84706a43470df686c21fc227d1db1df507636ad5f146dee0144 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 01:07:40,799 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 01:07:40,906 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 01:07:40,914 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 01:07:40,915 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 01:07:40,960 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 01:07:40,961 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 01:07:40,961 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 01:07:40,963 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 01:07:40,963 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 01:07:40,964 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 01:07:40,964 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 01:07:40,965 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 01:07:40,965 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 01:07:40,965 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 01:07:40,966 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 01:07:40,969 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 01:07:40,972 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 01:07:40,972 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 01:07:40,973 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 01:07:40,973 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 01:07:40,975 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 01:07:40,976 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 01:07:40,976 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 01:07:40,977 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 01:07:40,977 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 01:07:40,977 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 01:07:40,978 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 01:07:40,978 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 01:07:40,978 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 01:07:40,978 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 01:07:40,979 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 01:07:40,979 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 01:07:40,979 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 01:07:40,980 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 01:07:40,980 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 01:07:40,980 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 01:07:40,982 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 01:07:40,982 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:07:40,982 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 01:07:40,983 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 01:07:40,984 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 01:07:40,984 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 01:07:40,984 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 01:07:40,985 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 01:07:40,985 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 01:07:40,985 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 01:07:40,985 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_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/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_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje 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 -> 82b98e74657ce84706a43470df686c21fc227d1db1df507636ad5f146dee0144 [2024-11-09 01:07:41,307 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 01:07:41,341 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 01:07:41,344 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 01:07:41,347 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 01:07:41,347 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 01:07:41,349 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c Unable to find full path for "g++" [2024-11-09 01:07:43,571 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 01:07:43,753 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 01:07:43,754 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c [2024-11-09 01:07:43,763 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/data/922cbd97f/66117ff7db174efa80b9fa04d930307b/FLAG997a0e318 [2024-11-09 01:07:43,780 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/data/922cbd97f/66117ff7db174efa80b9fa04d930307b [2024-11-09 01:07:43,783 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 01:07:43,784 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 01:07:43,786 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 01:07:43,786 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 01:07:43,793 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 01:07:43,794 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:07:43" (1/1) ... [2024-11-09 01:07:43,795 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@29a9bdb5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:43, skipping insertion in model container [2024-11-09 01:07:43,796 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:07:43" (1/1) ... [2024-11-09 01:07:43,823 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 01:07:44,034 WARN L250 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_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c[1101,1114] [2024-11-09 01:07:44,064 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:07:44,078 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 01:07:44,090 WARN L250 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_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/sv-benchmarks/c/recursified_nla-digbench/recursified_fermat1-ll.c[1101,1114] [2024-11-09 01:07:44,111 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:07:44,131 INFO L204 MainTranslator]: Completed translation [2024-11-09 01:07:44,132 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44 WrapperNode [2024-11-09 01:07:44,132 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 01:07:44,133 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 01:07:44,133 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 01:07:44,133 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 01:07:44,142 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,152 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,172 INFO L138 Inliner]: procedures = 18, calls = 82, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 67 [2024-11-09 01:07:44,173 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 01:07:44,174 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 01:07:44,174 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 01:07:44,174 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 01:07:44,182 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,183 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,186 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,186 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,194 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,197 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,199 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,200 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,203 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 01:07:44,204 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 01:07:44,204 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 01:07:44,205 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 01:07:44,206 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (1/1) ... [2024-11-09 01:07:44,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:07:44,227 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:07:44,245 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-09 01:07:44,249 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-09 01:07:44,287 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 01:07:44,287 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_36_0 [2024-11-09 01:07:44,288 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_36_0 [2024-11-09 01:07:44,290 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 01:07:44,290 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 01:07:44,290 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 01:07:44,290 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-09 01:07:44,290 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2024-11-09 01:07:44,291 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_38_to_43_0 [2024-11-09 01:07:44,291 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_38_to_43_0 [2024-11-09 01:07:44,291 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_46_to_51_0 [2024-11-09 01:07:44,291 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_46_to_51_0 [2024-11-09 01:07:44,291 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 01:07:44,291 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 01:07:44,292 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2024-11-09 01:07:44,292 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 01:07:44,292 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 01:07:44,292 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-09 01:07:44,460 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 01:07:44,463 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 01:07:44,793 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-11-09 01:07:44,794 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 01:07:44,837 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 01:07:44,837 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-09 01:07:44,838 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:07:44 BoogieIcfgContainer [2024-11-09 01:07:44,838 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 01:07:44,841 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 01:07:44,841 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 01:07:44,844 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 01:07:44,844 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 01:07:43" (1/3) ... [2024-11-09 01:07:44,845 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@694e31ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:07:44, skipping insertion in model container [2024-11-09 01:07:44,845 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:07:44" (2/3) ... [2024-11-09 01:07:44,846 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@694e31ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:07:44, skipping insertion in model container [2024-11-09 01:07:44,846 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:07:44" (3/3) ... [2024-11-09 01:07:44,847 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_fermat1-ll.c [2024-11-09 01:07:44,869 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 01:07:44,869 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 01:07:44,966 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 01:07:44,976 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=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;@40edd6ce, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 01:07:44,977 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 01:07:44,983 INFO L276 IsEmpty]: Start isEmpty. Operand has 44 states, 25 states have (on average 1.32) internal successors, (33), 29 states have internal predecessors, (33), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 01:07:44,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-09 01:07:44,992 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:07:44,993 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:07:44,994 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:07:45,002 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:07:45,004 INFO L85 PathProgramCache]: Analyzing trace with hash 1940751987, now seen corresponding path program 1 times [2024-11-09 01:07:45,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:07:45,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [7321603] [2024-11-09 01:07:45,016 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:07:45,016 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:07:45,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:07:45,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1969634592] [2024-11-09 01:07:45,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:07:45,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:07:45,347 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:07:45,350 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:07:45,352 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 01:07:45,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:07:45,556 INFO L255 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 76 conjuncts are in the unsatisfiable core [2024-11-09 01:07:45,575 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:07:45,763 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:07:45,764 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:07:45,816 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:07:46,053 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:07:46,054 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:07:46,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 37 [2024-11-09 01:07:46,767 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 41 [2024-11-09 01:07:46,938 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:07:46,938 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 01:07:46,939 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:07:46,939 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [7321603] [2024-11-09 01:07:46,940 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:07:46,940 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1969634592] [2024-11-09 01:07:46,941 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1969634592] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:07:46,941 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:07:46,941 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-09 01:07:46,945 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1657949935] [2024-11-09 01:07:46,947 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:07:46,952 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 01:07:46,953 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:07:46,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 01:07:46,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-09 01:07:46,986 INFO L87 Difference]: Start difference. First operand has 44 states, 25 states have (on average 1.32) internal successors, (33), 29 states have internal predecessors, (33), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 9 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 7 states have internal predecessors, (9), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:07:47,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:07:47,996 INFO L93 Difference]: Finished difference Result 93 states and 133 transitions. [2024-11-09 01:07:47,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 01:07:47,999 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 7 states have internal predecessors, (9), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 16 [2024-11-09 01:07:48,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:07:48,009 INFO L225 Difference]: With dead ends: 93 [2024-11-09 01:07:48,010 INFO L226 Difference]: Without dead ends: 55 [2024-11-09 01:07:48,013 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-09 01:07:48,017 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 14 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 285 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 01:07:48,018 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 285 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 01:07:48,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-09 01:07:48,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 53. [2024-11-09 01:07:48,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 32 states have (on average 1.15625) internal successors, (37), 36 states have internal predecessors, (37), 13 states have call successors, (13), 7 states have call predecessors, (13), 7 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2024-11-09 01:07:48,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 63 transitions. [2024-11-09 01:07:48,100 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 63 transitions. Word has length 16 [2024-11-09 01:07:48,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:07:48,102 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 63 transitions. [2024-11-09 01:07:48,102 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 7 states have internal predecessors, (9), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:07:48,103 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 63 transitions. [2024-11-09 01:07:48,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-09 01:07:48,106 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:07:48,106 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:07:48,130 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-09 01:07:48,307 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-09 01:07:48,307 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:07:48,308 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:07:48,308 INFO L85 PathProgramCache]: Analyzing trace with hash -971249846, now seen corresponding path program 1 times [2024-11-09 01:07:48,309 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:07:48,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1884059959] [2024-11-09 01:07:48,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:07:48,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:07:48,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:07:48,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [208468023] [2024-11-09 01:07:48,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:07:48,414 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:07:48,414 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:07:48,417 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:07:48,422 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 01:07:48,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:07:48,635 WARN L253 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 117 conjuncts are in the unsatisfiable core [2024-11-09 01:07:48,641 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:07:48,659 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:07:48,659 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:07:48,681 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:07:48,810 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:07:48,811 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:07:48,816 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 37 [2024-11-09 01:07:50,361 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 89 treesize of output 45 [2024-11-09 01:07:50,506 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:07:50,506 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:08:02,841 WARN L851 $PredicateComparison]: unable to prove that (forall ((|ULTIMATE.start_main_~#r~0#1.offset| Int) (|ULTIMATE.start_main_~R~0#1| Int) (|ULTIMATE.start_main_~#u~0#1.offset| Int)) (let ((.cse5 (let ((.cse6 (store |c_#memory_int| |c_ULTIMATE.start_main_~#u~0#1.base| (store (select |c_#memory_int| |c_ULTIMATE.start_main_~#u~0#1.base|) |ULTIMATE.start_main_~#u~0#1.offset| (+ (* 2 |ULTIMATE.start_main_~R~0#1|) 1))))) (store .cse6 |c_ULTIMATE.start_main_~#v~0#1.base| (store (select .cse6 |c_ULTIMATE.start_main_~#v~0#1.base|) |c_ULTIMATE.start_main_~#v~0#1.offset| 1))))) (let ((.cse4 (* |ULTIMATE.start_main_~R~0#1| |ULTIMATE.start_main_~R~0#1|)) (.cse1 (select (select .cse5 |c_ULTIMATE.start_main_~#A~0#1.base|) |c_ULTIMATE.start_main_~#A~0#1.offset|))) (let ((.cse3 (store .cse5 |c_ULTIMATE.start_main_~#r~0#1.base| (store (select .cse5 |c_ULTIMATE.start_main_~#r~0#1.base|) |ULTIMATE.start_main_~#r~0#1.offset| (+ .cse4 (* (- 1) .cse1)))))) (let ((.cse2 (select (select .cse3 |c_ULTIMATE.start_main_~#u~0#1.base|) |ULTIMATE.start_main_~#u~0#1.offset|)) (.cse0 (select (select .cse3 |c_ULTIMATE.start_main_~#v~0#1.base|) |c_ULTIMATE.start_main_~#v~0#1.offset|))) (= (+ (* 2 .cse0) (* .cse1 4) (* .cse2 .cse2)) (+ (* (select (select .cse3 |c_ULTIMATE.start_main_~#A~0#1.base|) |c_ULTIMATE.start_main_~#A~0#1.offset|) 4) (* .cse4 4) (* 2 .cse2) (* .cse0 .cse0)))))))) is different from false [2024-11-09 01:08:02,872 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:08:02,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1884059959] [2024-11-09 01:08:02,873 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:08:02,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [208468023] [2024-11-09 01:08:02,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [208468023] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:08:02,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [837214989] [2024-11-09 01:08:02,903 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2024-11-09 01:08:02,903 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:08:02,908 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:08:02,915 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:08:02,919 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:08:03,730 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 172 for LOIs [2024-11-09 01:08:03,826 INFO L197 IcfgInterpreter]: Interpreting procedure func_to_recursive_line_33_to_36_0 with input of size 122 for LOIs [2024-11-09 01:08:04,592 INFO L197 IcfgInterpreter]: Interpreting procedure func_to_recursive_line_38_to_43_0 with input of size 141 for LOIs [2024-11-09 01:08:04,940 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 230 for LOIs [2024-11-09 01:08:06,083 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:09:46,394 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [837214989] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:09:46,395 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:09:46,395 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [19] imperfect sequences [12] total 30 [2024-11-09 01:09:46,396 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [112901338] [2024-11-09 01:09:46,396 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:09:46,396 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 01:09:46,397 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:09:46,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 01:09:46,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=1246, Unknown=17, NotChecked=72, Total=1482 [2024-11-09 01:09:46,399 INFO L87 Difference]: Start difference. First operand 53 states and 63 transitions. Second operand has 20 states, 14 states have (on average 1.0714285714285714) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 01:09:53,236 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse0 (+ |c_#StackHeapBarrier| 1)) (.cse10 (= |c___VERIFIER_assert_#in~cond| 1))) (and (= |c___VERIFIER_assert_#in~cond| c___VERIFIER_assert_~cond) (<= 1 |c_#StackHeapBarrier|) (or (exists ((|v_#valid_22| (Array Int Int)) (|v_#memory_int_43| (Array Int (Array Int Int))) (|v_#memory_int_44| (Array Int (Array Int Int))) (|v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| Int) (|v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| Int) (|v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| Int) (|v_ULTIMATE.start_main_~R~0#1_16| Int) (|v_#length_11| (Array Int Int)) (|v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| Int)) (let ((.cse2 (* 2 |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse9 (store |v_#valid_22| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| 1))) (let ((.cse8 (store .cse9 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| 1)) (.cse5 (let ((.cse11 (store |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| (store (select |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) 0 (+ .cse2 1))))) (store .cse11 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| (store (select .cse11 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) 0 1))))) (let ((.cse6 (select (select .cse5 |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0)) (.cse1 (* |v_ULTIMATE.start_main_~R~0#1_16| |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse3 (select (select |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0)) (.cse4 (store .cse8 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| 1)) (.cse7 (select |v_#memory_int_43| 1))) (and (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) (<= (+ 2 .cse1) (+ .cse2 .cse3)) (<= .cse3 2147483647) (= 0 (select .cse4 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|)) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|) (= (select |v_#length_11| 2) 13) (= (select |v_#valid_22| 3) 1) (= (select |v_#valid_22| 2) 1) (= (select |v_#valid_22| 1) 1) (= (select |v_#length_11| 3) 12) (= (store .cse5 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| (store (select .cse5 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|) 0 (+ (* (- 1) .cse6) .cse1))) |c_#memory_int|) (= (mod .cse3 2) 1) (= (select |v_#valid_22| 0) 0) (= |c_#length| (store (store (store (store |v_#length_11| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| 4) |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| 8) |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| 8) |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| 8)) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) (= (select .cse7 1) 0) (not (= .cse6 .cse1)) (= |v_#memory_int_44| (store |v_#memory_int_43| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| (store (select |v_#memory_int_43| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0 .cse3))) (= (select .cse8 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) 0) (= |c_#valid| (store .cse4 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| 1)) (= (select .cse9 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) 0) .cse10 (= 2 (select |v_#length_11| 1)) (= (select |v_#valid_22| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0) (= (select .cse7 0) 48)))))) (exists ((|v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| Int) (|v_#valid_22| (Array Int Int)) (|v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| Int) (|v_#memory_int_43| (Array Int (Array Int Int))) (|v_#memory_int_44| (Array Int (Array Int Int))) (|v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| Int) (|v_ULTIMATE.start_main_~R~0#1_16| Int) (|v_#length_11| (Array Int Int)) (|v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| Int)) (let ((.cse17 (store |v_#valid_22| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| 1))) (let ((.cse16 (store .cse17 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| 1))) (let ((.cse13 (store .cse16 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| 1)) (.cse12 (select (select |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0)) (.cse14 (* |v_ULTIMATE.start_main_~R~0#1_16| |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse15 (* 2 |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse18 (select |v_#memory_int_43| 1))) (and (= |v_#memory_int_44| (store |v_#memory_int_43| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| (store (select |v_#memory_int_43| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0 .cse12))) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) (= |c_#valid| (store .cse13 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| 1)) (= (select |v_#length_11| 2) 13) (= (select |v_#valid_22| 3) 1) (= (select |v_#valid_22| 2) 1) (= (select .cse13 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) 0) (= (select |v_#valid_22| 1) 1) (<= .cse12 2147483647) (= (select |v_#length_11| 3) 12) (= (select |v_#valid_22| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0) (= (store (store (store (store |v_#length_11| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| 4) |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| 8) |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| 8) |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| 8) |c_#length|) (= (select |v_#valid_22| 0) 0) (= (mod .cse12 2) 1) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) (<= (+ 2 .cse14) (+ .cse12 .cse15)) (= (select .cse16 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) 0) (= (select .cse17 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) 0) (= (select .cse18 1) 0) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) (= |c_#memory_int| (let ((.cse19 (let ((.cse20 (store |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| (store (select |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) 0 (+ .cse15 1))))) (store .cse20 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| (store (select .cse20 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) 0 1))))) (store .cse19 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| (store (select .cse19 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) 0 (+ (* (- 1) (select (select .cse19 |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0)) .cse14))))) .cse10 (= 2 (select |v_#length_11| 1)) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) (= (select .cse18 0) 48))))))) (or (and .cse10 (exists ((|v_#valid_22| (Array Int Int)) (|v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| Int) (|v_#memory_int_43| (Array Int (Array Int Int))) (|v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| Int) (|v_#memory_int_44| (Array Int (Array Int Int))) (|v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| Int) (|v_#length_11| (Array Int Int)) (|v_ULTIMATE.start_main_~R~0#1_16| Int) (|v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| Int)) (let ((.cse26 (store |v_#valid_22| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| 1))) (let ((.cse25 (store .cse26 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| 1))) (let ((.cse22 (store .cse25 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| 1)) (.cse21 (select (select |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0)) (.cse23 (* |v_ULTIMATE.start_main_~R~0#1_16| |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse24 (* 2 |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse27 (select |v_#memory_int_43| 1))) (and (= |v_#memory_int_44| (store |v_#memory_int_43| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| (store (select |v_#memory_int_43| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0 .cse21))) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) (= |c_#valid| (store .cse22 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| 1)) (= (select |v_#length_11| 2) 13) (= (select |v_#valid_22| 3) 1) (= (select |v_#valid_22| 2) 1) (= (select .cse22 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) 0) (= (select |v_#valid_22| 1) 1) (<= .cse21 2147483647) (= (select |v_#length_11| 3) 12) (= (select |v_#valid_22| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0) (= (store (store (store (store |v_#length_11| |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4| 4) |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| 8) |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| 8) |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| 8) |c_#length|) (= (select |v_#valid_22| 0) 0) (= (mod .cse21 2) 1) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) (<= (+ 2 .cse23) (+ .cse21 .cse24)) (= (select .cse25 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) 0) (= (select .cse26 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) 0) (= (select .cse27 1) 0) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) (= |c_#memory_int| (let ((.cse28 (let ((.cse29 (store |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4| (store (select |v_#memory_int_44| |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) 0 (+ .cse24 1))))) (store .cse29 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4| (store (select .cse29 |v_func_to_recursive_line_33_to_36_0_#in~v.base_BEFORE_CALL_4|) 0 1))))) (store .cse28 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4| (store (select .cse28 |v_func_to_recursive_line_33_to_36_0_#in~r.base_BEFORE_CALL_4|) 0 (+ (* (- 1) (select (select .cse28 |v_func_to_recursive_line_33_to_36_0_#in~A.base_BEFORE_CALL_4|) 0)) .cse23))))) (= 2 (select |v_#length_11| 1)) (<= .cse0 |v_func_to_recursive_line_33_to_36_0_#in~u.base_BEFORE_CALL_4|) (= (select .cse27 0) 48))))))) (and (exists ((|v_#valid_22| (Array Int Int)) (|v_#memory_int_43| (Array Int (Array Int Int))) (|v_#memory_int_44| (Array Int (Array Int Int))) (|v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| Int) (|v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| Int) (|v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| Int) (|v_#length_11| (Array Int Int)) (|v_ULTIMATE.start_main_~R~0#1_16| Int) (|v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| Int)) (let ((.cse31 (* 2 |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse38 (store |v_#valid_22| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| 1))) (let ((.cse37 (store .cse38 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| 1)) (.cse34 (let ((.cse39 (store |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| (store (select |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) 0 (+ .cse31 1))))) (store .cse39 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| (store (select .cse39 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) 0 1))))) (let ((.cse35 (select (select .cse34 |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0)) (.cse30 (* |v_ULTIMATE.start_main_~R~0#1_16| |v_ULTIMATE.start_main_~R~0#1_16|)) (.cse32 (select (select |v_#memory_int_44| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0)) (.cse33 (store .cse37 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| 1)) (.cse36 (select |v_#memory_int_43| 1))) (and (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) (<= (+ 2 .cse30) (+ .cse31 .cse32)) (<= .cse32 2147483647) (= 0 (select .cse33 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|)) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|) (= (select |v_#length_11| 2) 13) (= (select |v_#valid_22| 3) 1) (= (select |v_#valid_22| 2) 1) (= (select |v_#valid_22| 1) 1) (= (select |v_#length_11| 3) 12) (= (store .cse34 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| (store (select .cse34 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1|) 0 (+ (* (- 1) .cse35) .cse30))) |c_#memory_int|) (= (mod .cse32 2) 1) (= (select |v_#valid_22| 0) 0) (= |c_#length| (store (store (store (store |v_#length_11| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| 4) |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1| 8) |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1| 8) |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| 8)) (<= .cse0 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) (= (select .cse36 1) 0) (not (= .cse35 .cse30)) (= |v_#memory_int_44| (store |v_#memory_int_43| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1| (store (select |v_#memory_int_43| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0 .cse32))) (= (select .cse37 |v_func_to_recursive_line_38_to_43_0_#in~v.base_BEFORE_CALL_1|) 0) (= |c_#valid| (store .cse33 |v_func_to_recursive_line_38_to_43_0_#in~r.base_BEFORE_CALL_1| 1)) (= (select .cse38 |v_func_to_recursive_line_38_to_43_0_#in~u.base_BEFORE_CALL_1|) 0) (= 2 (select |v_#length_11| 1)) (= (select |v_#valid_22| |v_func_to_recursive_line_38_to_43_0_#in~A.base_BEFORE_CALL_1|) 0) (= (select .cse36 0) 48)))))) .cse10)))) is different from false [2024-11-09 01:09:57,944 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.65s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:09:59,994 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.17s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:10,998 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:15,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:10:15,991 INFO L93 Difference]: Finished difference Result 69 states and 82 transitions. [2024-11-09 01:10:15,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 01:10:15,993 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 14 states have (on average 1.0714285714285714) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2024-11-09 01:10:15,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:10:15,994 INFO L225 Difference]: With dead ends: 69 [2024-11-09 01:10:15,995 INFO L226 Difference]: Without dead ends: 67 [2024-11-09 01:10:15,996 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 30 SyntacticMatches, 3 SemanticMatches, 38 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 378 ImplicationChecksByTransitivity, 115.1s TimeCoverageRelationStatistics Valid=149, Invalid=1247, Unknown=18, NotChecked=146, Total=1560 [2024-11-09 01:10:15,997 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 522 mSolverCounterSat, 5 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 27.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 546 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 522 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 18 IncrementalHoareTripleChecker+Unchecked, 27.5s IncrementalHoareTripleChecker+Time [2024-11-09 01:10:15,998 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 247 Invalid, 546 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 522 Invalid, 1 Unknown, 18 Unchecked, 27.5s Time] [2024-11-09 01:10:15,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-09 01:10:16,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2024-11-09 01:10:16,033 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 40 states have (on average 1.15) internal successors, (46), 45 states have internal predecessors, (46), 15 states have call successors, (15), 9 states have call predecessors, (15), 9 states have return successors, (16), 13 states have call predecessors, (16), 14 states have call successors, (16) [2024-11-09 01:10:16,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 77 transitions. [2024-11-09 01:10:16,035 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 77 transitions. Word has length 26 [2024-11-09 01:10:16,036 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:10:16,036 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 77 transitions. [2024-11-09 01:10:16,036 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 14 states have (on average 1.0714285714285714) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 01:10:16,037 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 77 transitions. [2024-11-09 01:10:16,037 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-09 01:10:16,037 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:10:16,038 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:10:16,047 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 01:10:16,238 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:10:16,239 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:10:16,239 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:10:16,239 INFO L85 PathProgramCache]: Analyzing trace with hash -169293736, now seen corresponding path program 1 times [2024-11-09 01:10:16,239 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:10:16,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1790948459] [2024-11-09 01:10:16,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:10:16,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:10:16,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:10:16,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1665774024] [2024-11-09 01:10:16,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:10:16,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:10:16,331 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:10:16,333 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:10:16,339 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 01:10:16,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:10:16,531 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-09 01:10:16,535 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:10:16,561 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:10:16,575 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:10:16,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:10:17,262 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:10:17,263 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:10:17,347 INFO L349 Elim1Store]: treesize reduction 78, result has 24.3 percent of original size [2024-11-09 01:10:17,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 125 treesize of output 89 [2024-11-09 01:10:19,799 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 109 treesize of output 57 [2024-11-09 01:10:20,751 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 01:10:20,751 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 01:10:20,752 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:10:20,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1790948459] [2024-11-09 01:10:20,752 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:10:20,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1665774024] [2024-11-09 01:10:20,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1665774024] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:10:20,754 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:10:20,754 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18] imperfect sequences [] total 18 [2024-11-09 01:10:20,754 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [175558676] [2024-11-09 01:10:20,754 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:10:20,755 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-09 01:10:20,755 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:10:20,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-09 01:10:20,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=259, Unknown=2, NotChecked=0, Total=306 [2024-11-09 01:10:20,756 INFO L87 Difference]: Start difference. First operand 65 states and 77 transitions. Second operand has 18 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 12 states have internal predecessors, (17), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:10:22,800 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:29,019 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:31,951 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:34,126 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.05s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:37,079 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.06s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:39,140 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:42,973 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.08s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:45,784 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:50,316 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:10:52,359 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:11:00,909 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:11:00,910 INFO L93 Difference]: Finished difference Result 113 states and 138 transitions. [2024-11-09 01:11:00,910 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-09 01:11:00,911 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 12 states have internal predecessors, (17), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 26 [2024-11-09 01:11:00,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:11:00,913 INFO L225 Difference]: With dead ends: 113 [2024-11-09 01:11:00,913 INFO L226 Difference]: Without dead ends: 101 [2024-11-09 01:11:00,914 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=129, Invalid=857, Unknown=6, NotChecked=0, Total=992 [2024-11-09 01:11:00,915 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 62 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 611 mSolverCounterSat, 43 mSolverCounterUnsat, 28 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 36.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 682 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 611 IncrementalHoareTripleChecker+Invalid, 28 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 36.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:11:00,916 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 203 Invalid, 682 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 611 Invalid, 28 Unknown, 0 Unchecked, 36.1s Time] [2024-11-09 01:11:00,917 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2024-11-09 01:11:00,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 99. [2024-11-09 01:11:00,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 60 states have (on average 1.1333333333333333) internal successors, (68), 64 states have internal predecessors, (68), 23 states have call successors, (23), 14 states have call predecessors, (23), 15 states have return successors, (32), 21 states have call predecessors, (32), 22 states have call successors, (32) [2024-11-09 01:11:00,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 123 transitions. [2024-11-09 01:11:00,954 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 123 transitions. Word has length 26 [2024-11-09 01:11:00,955 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:11:00,955 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 123 transitions. [2024-11-09 01:11:00,955 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 12 states have internal predecessors, (17), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:11:00,955 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 123 transitions. [2024-11-09 01:11:00,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 01:11:00,956 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:11:00,957 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:11:00,967 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 01:11:01,157 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:11:01,158 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:11:01,158 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:11:01,158 INFO L85 PathProgramCache]: Analyzing trace with hash 1614725153, now seen corresponding path program 1 times [2024-11-09 01:11:01,158 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:11:01,158 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1423426564] [2024-11-09 01:11:01,158 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:11:01,158 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:11:01,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:11:01,281 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [685234097] [2024-11-09 01:11:01,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:11:01,281 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:11:01,281 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:11:01,283 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:11:01,296 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 01:11:01,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:11:01,639 WARN L253 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 163 conjuncts are in the unsatisfiable core [2024-11-09 01:11:01,646 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:11:01,667 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:11:01,668 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:11:01,700 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:11:01,991 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:11:01,992 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:11:01,997 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 101 treesize of output 48 [2024-11-09 01:11:07,923 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:11:07,973 INFO L349 Elim1Store]: treesize reduction 22, result has 35.3 percent of original size [2024-11-09 01:11:07,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 135 treesize of output 82 [2024-11-09 01:11:08,673 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 106 treesize of output 50 [2024-11-09 01:11:09,944 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 5 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 01:11:09,944 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:11:57,809 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:11:57,809 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1423426564] [2024-11-09 01:11:57,809 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:11:57,809 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [685234097] [2024-11-09 01:11:57,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [685234097] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:11:57,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [194181801] [2024-11-09 01:11:57,813 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2024-11-09 01:11:57,813 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:11:57,815 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:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:426) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:312) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:273) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) 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) [2024-11-09 01:11:57,817 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:11:57,817 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-09 01:11:57,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [644386463] [2024-11-09 01:11:57,818 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 01:11:57,818 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 01:11:57,818 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:11:57,819 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 01:11:57,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=992, Unknown=14, NotChecked=0, Total=1122 [2024-11-09 01:11:57,821 INFO L87 Difference]: Start difference. First operand 99 states and 123 transitions. Second operand has 21 states, 16 states have (on average 1.5) internal successors, (24), 16 states have internal predecessors, (24), 8 states have call successors, (8), 8 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:12:00,237 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:04,699 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:06,754 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:08,845 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:10,811 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.86s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:24,266 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:26,355 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:28,215 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:33,430 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:35,444 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:41,184 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:42,982 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.80s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:12:45,738 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:47,769 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:49,126 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.31s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:51,140 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:53,248 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:55,288 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:57,377 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:12:59,631 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.75s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:01,647 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:05,221 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:07,276 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:09,325 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:10,647 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:13,324 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:14,809 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.01s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:13:14,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:13:14,980 INFO L93 Difference]: Finished difference Result 160 states and 207 transitions. [2024-11-09 01:13:14,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-09 01:13:14,981 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 1.5) internal successors, (24), 16 states have internal predecessors, (24), 8 states have call successors, (8), 8 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 36 [2024-11-09 01:13:14,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:13:14,984 INFO L225 Difference]: With dead ends: 160 [2024-11-09 01:13:14,984 INFO L226 Difference]: Without dead ends: 158 [2024-11-09 01:13:14,986 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 29 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 424 ImplicationChecksByTransitivity, 73.2s TimeCoverageRelationStatistics Valid=224, Invalid=1828, Unknown=18, NotChecked=0, Total=2070 [2024-11-09 01:13:14,987 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 99 mSDsluCounter, 414 mSDsCounter, 0 mSdLazyCounter, 779 mSolverCounterSat, 16 mSolverCounterUnsat, 17 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 55.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 456 SdHoareTripleChecker+Invalid, 812 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 779 IncrementalHoareTripleChecker+Invalid, 17 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 56.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:13:14,987 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 456 Invalid, 812 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 779 Invalid, 17 Unknown, 0 Unchecked, 56.1s Time] [2024-11-09 01:13:14,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-11-09 01:13:15,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 153. [2024-11-09 01:13:15,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 91 states have (on average 1.1428571428571428) internal successors, (104), 99 states have internal predecessors, (104), 36 states have call successors, (36), 20 states have call predecessors, (36), 25 states have return successors, (59), 35 states have call predecessors, (59), 34 states have call successors, (59) [2024-11-09 01:13:15,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 199 transitions. [2024-11-09 01:13:15,069 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 199 transitions. Word has length 36 [2024-11-09 01:13:15,070 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:13:15,070 INFO L471 AbstractCegarLoop]: Abstraction has 153 states and 199 transitions. [2024-11-09 01:13:15,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 1.5) internal successors, (24), 16 states have internal predecessors, (24), 8 states have call successors, (8), 8 states have call predecessors, (8), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:13:15,070 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 199 transitions. [2024-11-09 01:13:15,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-09 01:13:15,072 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:13:15,072 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:13:15,097 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 01:13:15,272 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:13:15,273 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:13:15,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:13:15,274 INFO L85 PathProgramCache]: Analyzing trace with hash -730228997, now seen corresponding path program 1 times [2024-11-09 01:13:15,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:13:15,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [645594698] [2024-11-09 01:13:15,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:13:15,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:13:15,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:13:15,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [781915629] [2024-11-09 01:13:15,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:13:15,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:13:15,436 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:13:15,440 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:13:15,446 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 01:13:15,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:13:15,815 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 124 conjuncts are in the unsatisfiable core [2024-11-09 01:13:15,821 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:13:15,834 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:13:15,847 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:13:15,847 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:13:16,019 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:13:16,021 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:13:16,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 37 [2024-11-09 01:13:17,734 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 89 treesize of output 45 [2024-11-09 01:13:17,918 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:13:17,918 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:13:23,474 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:13:23,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [645594698] [2024-11-09 01:13:23,474 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:13:23,474 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [781915629] [2024-11-09 01:13:23,474 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [781915629] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:13:23,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [339335941] [2024-11-09 01:13:23,478 INFO L159 IcfgInterpreter]: Started Sifa with 31 locations of interest [2024-11-09 01:13:23,478 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:13:23,478 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:13:23,479 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:13:23,479 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:13:24,230 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 172 for LOIs [2024-11-09 01:13:24,336 INFO L197 IcfgInterpreter]: Interpreting procedure func_to_recursive_line_33_to_36_0 with input of size 122 for LOIs [2024-11-09 01:13:25,853 INFO L197 IcfgInterpreter]: Interpreting procedure func_to_recursive_line_46_to_51_0 with input of size 157 for LOIs [2024-11-09 01:13:26,637 INFO L197 IcfgInterpreter]: Interpreting procedure func_to_recursive_line_38_to_43_0 with input of size 141 for LOIs [2024-11-09 01:13:27,704 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 3 for LOIs [2024-11-09 01:13:27,714 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:14:55,572 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2040#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:14:55,572 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:14:55,572 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:14:55,572 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-11-09 01:14:55,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1440195360] [2024-11-09 01:14:55,573 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 01:14:55,573 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 01:14:55,573 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:14:55,574 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 01:14:55,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=1681, Unknown=21, NotChecked=0, Total=1892 [2024-11-09 01:14:55,575 INFO L87 Difference]: Start difference. First operand 153 states and 199 transitions. Second operand has 14 states, 12 states have (on average 2.0) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (8), 6 states have call predecessors, (8), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 01:15:25,918 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:15:31,550 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.54s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:34,956 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:36,967 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:15:37,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:15:37,482 INFO L93 Difference]: Finished difference Result 161 states and 205 transitions. [2024-11-09 01:15:37,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 01:15:37,483 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.0) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (8), 6 states have call predecessors, (8), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 38 [2024-11-09 01:15:37,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:15:37,486 INFO L225 Difference]: With dead ends: 161 [2024-11-09 01:15:37,486 INFO L226 Difference]: Without dead ends: 159 [2024-11-09 01:15:37,488 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 43 SyntacticMatches, 5 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 736 ImplicationChecksByTransitivity, 124.8s TimeCoverageRelationStatistics Valid=279, Invalid=2444, Unknown=33, NotChecked=0, Total=2756 [2024-11-09 01:15:37,489 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 60 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 427 mSolverCounterSat, 38 mSolverCounterUnsat, 10 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 475 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 427 IncrementalHoareTripleChecker+Invalid, 10 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.8s IncrementalHoareTripleChecker+Time [2024-11-09 01:15:37,489 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 200 Invalid, 475 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 427 Invalid, 10 Unknown, 0 Unchecked, 10.8s Time] [2024-11-09 01:15:37,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2024-11-09 01:15:37,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 157. [2024-11-09 01:15:37,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 94 states have (on average 1.1382978723404256) internal successors, (107), 102 states have internal predecessors, (107), 36 states have call successors, (36), 21 states have call predecessors, (36), 26 states have return successors, (59), 35 states have call predecessors, (59), 34 states have call successors, (59) [2024-11-09 01:15:37,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 202 transitions. [2024-11-09 01:15:37,581 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 202 transitions. Word has length 38 [2024-11-09 01:15:37,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:15:37,581 INFO L471 AbstractCegarLoop]: Abstraction has 157 states and 202 transitions. [2024-11-09 01:15:37,582 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.0) internal successors, (24), 11 states have internal predecessors, (24), 5 states have call successors, (8), 6 states have call predecessors, (8), 3 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 01:15:37,582 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 202 transitions. [2024-11-09 01:15:37,583 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-09 01:15:37,583 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:15:37,584 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:15:37,602 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 01:15:37,784 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:37,785 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:15:37,785 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:15:37,785 INFO L85 PathProgramCache]: Analyzing trace with hash 986036280, now seen corresponding path program 2 times [2024-11-09 01:15:37,785 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:15:37,785 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [364202382] [2024-11-09 01:15:37,786 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:15:37,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:15:37,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:15:37,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [704742837] [2024-11-09 01:15:37,881 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 01:15:37,881 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:15:37,881 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:15:37,883 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:15:37,888 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 01:15:39,854 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 01:15:39,854 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:15:39,861 WARN L253 TraceCheckSpWp]: Trace formula consists of 356 conjuncts, 203 conjuncts are in the unsatisfiable core [2024-11-09 01:15:39,868 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:15:39,897 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-09 01:15:39,897 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 27 [2024-11-09 01:15:40,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 43 [2024-11-09 01:15:40,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:15:40,075 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 16 [2024-11-09 01:15:40,087 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 5 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 11 [2024-11-09 01:15:41,649 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:15:41,784 INFO L349 Elim1Store]: treesize reduction 67, result has 31.6 percent of original size [2024-11-09 01:15:41,784 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 5 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 96 treesize of output 85 [2024-11-09 01:15:43,655 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:15:43,667 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-09 01:15:43,668 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 1 case distinctions, treesize of input 88 treesize of output 51 [2024-11-09 01:15:44,525 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 01:15:44,525 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 1 case distinctions, treesize of input 78 treesize of output 42 [2024-11-09 01:15:45,087 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 3 proven. 26 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 01:15:45,088 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:16:16,552 WARN L873 $PredicateComparison]: unable to prove that (forall ((|func_to_recursive_line_38_to_43_0_#in~r.offset| Int)) (let ((.cse13 (select |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~r.base))) (let ((.cse2 (select .cse13 |func_to_recursive_line_38_to_43_0_#in~r.offset|)) (.cse0 (select (select |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~v.base) c_func_to_recursive_line_33_to_36_0_~v.offset))) (or (not (let ((.cse1 (select (select |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~u.base) c_func_to_recursive_line_33_to_36_0_~u.offset))) (= (+ (* .cse0 2) (* .cse1 .cse1)) (+ (* (select (select |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~A.base) c_func_to_recursive_line_33_to_36_0_~A.offset) 4) (* .cse2 4) (* 2 .cse1) (* .cse0 .cse0))))) (let ((.cse11 (store |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~r.base (store .cse13 |func_to_recursive_line_38_to_43_0_#in~r.offset| (+ .cse2 (* (- 1) .cse0)))))) (let ((.cse12 (select .cse11 c_func_to_recursive_line_33_to_36_0_~v.base))) (let ((.cse10 (select .cse12 c_func_to_recursive_line_33_to_36_0_~v.offset))) (let ((.cse8 (store .cse12 c_func_to_recursive_line_33_to_36_0_~v.offset (+ 2 .cse10)))) (let ((.cse6 (let ((.cse9 (select (store .cse11 c_func_to_recursive_line_33_to_36_0_~v.base .cse8) c_func_to_recursive_line_33_to_36_0_~r.base))) (store .cse9 |func_to_recursive_line_38_to_43_0_#in~r.offset| (+ (- 2) (select .cse9 |func_to_recursive_line_38_to_43_0_#in~r.offset|) (* (- 1) .cse10)))))) (let ((.cse7 (select (store (store |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~v.base .cse8) c_func_to_recursive_line_33_to_36_0_~r.base .cse6) c_func_to_recursive_line_33_to_36_0_~v.base))) (let ((.cse3 (select .cse7 c_func_to_recursive_line_33_to_36_0_~v.offset))) (let ((.cse5 (store (store |c_#memory_int| c_func_to_recursive_line_33_to_36_0_~r.base .cse6) c_func_to_recursive_line_33_to_36_0_~v.base (store .cse7 c_func_to_recursive_line_33_to_36_0_~v.offset (+ 2 .cse3))))) (let ((.cse4 (select (select .cse5 c_func_to_recursive_line_33_to_36_0_~u.base) c_func_to_recursive_line_33_to_36_0_~u.offset))) (= (+ (* .cse3 .cse3) (* 2 .cse3) (* 2 .cse4) (* (select (select .cse5 c_func_to_recursive_line_33_to_36_0_~r.base) |func_to_recursive_line_38_to_43_0_#in~r.offset|) 4) (* (select (select .cse5 c_func_to_recursive_line_33_to_36_0_~A.base) c_func_to_recursive_line_33_to_36_0_~A.offset) 4)) (* .cse4 .cse4))))))))))))))) is different from true [2024-11-09 01:16:17,097 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:16:17,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [364202382] [2024-11-09 01:16:17,097 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:16:17,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [704742837] [2024-11-09 01:16:17,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [704742837] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:16:17,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [708061343] [2024-11-09 01:16:17,100 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2024-11-09 01:16:17,100 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:16:17,101 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:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:426) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:312) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:273) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) 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) [2024-11-09 01:16:17,102 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:16:17,102 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2024-11-09 01:16:17,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1189767961] [2024-11-09 01:16:17,102 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 01:16:17,103 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 01:16:17,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:16:17,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 01:16:17,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=876, Unknown=9, NotChecked=60, Total=1056 [2024-11-09 01:16:17,104 INFO L87 Difference]: Start difference. First operand 157 states and 202 transitions. Second operand has 21 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 16 states have internal predecessors, (30), 7 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-09 01:16:39,898 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:16:42,020 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:16:44,194 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:16:45,833 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:16:49,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:16:49,391 INFO L93 Difference]: Finished difference Result 212 states and 272 transitions. [2024-11-09 01:16:49,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-09 01:16:49,392 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 16 states have internal predecessors, (30), 7 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 46 [2024-11-09 01:16:49,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:16:49,395 INFO L225 Difference]: With dead ends: 212 [2024-11-09 01:16:49,395 INFO L226 Difference]: Without dead ends: 210 [2024-11-09 01:16:49,396 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 39 SyntacticMatches, 5 SemanticMatches, 41 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 341 ImplicationChecksByTransitivity, 50.0s TimeCoverageRelationStatistics Valid=213, Invalid=1500, Unknown=13, NotChecked=80, Total=1806 [2024-11-09 01:16:49,397 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 95 mSDsluCounter, 669 mSDsCounter, 0 mSdLazyCounter, 933 mSolverCounterSat, 14 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 735 SdHoareTripleChecker+Invalid, 950 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 933 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.8s IncrementalHoareTripleChecker+Time [2024-11-09 01:16:49,397 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [98 Valid, 735 Invalid, 950 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 933 Invalid, 3 Unknown, 0 Unchecked, 14.8s Time] [2024-11-09 01:16:49,399 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2024-11-09 01:16:49,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 205. [2024-11-09 01:16:49,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 205 states, 123 states have (on average 1.146341463414634) internal successors, (141), 133 states have internal predecessors, (141), 47 states have call successors, (47), 27 states have call predecessors, (47), 34 states have return successors, (76), 47 states have call predecessors, (76), 44 states have call successors, (76) [2024-11-09 01:16:49,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 205 states to 205 states and 264 transitions. [2024-11-09 01:16:49,498 INFO L78 Accepts]: Start accepts. Automaton has 205 states and 264 transitions. Word has length 46 [2024-11-09 01:16:49,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:16:49,499 INFO L471 AbstractCegarLoop]: Abstraction has 205 states and 264 transitions. [2024-11-09 01:16:49,499 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 16 states have internal predecessors, (30), 7 states have call successors, (10), 8 states have call predecessors, (10), 4 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-09 01:16:49,499 INFO L276 IsEmpty]: Start isEmpty. Operand 205 states and 264 transitions. [2024-11-09 01:16:49,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-09 01:16:49,500 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:16:49,501 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:16:49,509 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-09 01:16:49,701 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:49,702 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:16:49,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:16:49,702 INFO L85 PathProgramCache]: Analyzing trace with hash -1408369266, now seen corresponding path program 1 times [2024-11-09 01:16:49,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:16:49,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803300801] [2024-11-09 01:16:49,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:16:49,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:16:49,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:16:49,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1673253766] [2024-11-09 01:16:49,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:16:49,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:49,810 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:16:49,816 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:16:49,817 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 01:16:50,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:16:50,554 WARN L253 TraceCheckSpWp]: Trace formula consists of 351 conjuncts, 187 conjuncts are in the unsatisfiable core [2024-11-09 01:16:50,561 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:16:50,580 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:16:50,593 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:16:50,594 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:16:50,826 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:16:50,828 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:16:50,833 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 37 [2024-11-09 01:16:54,055 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:16:54,062 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 116 treesize of output 67 [2024-11-09 01:16:54,630 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2024-11-09 01:16:54,631 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 1 case distinctions, treesize of input 109 treesize of output 57 [2024-11-09 01:16:54,871 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 01:16:54,872 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:17:14,854 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:17:14,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1803300801] [2024-11-09 01:17:14,855 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:17:14,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1673253766] [2024-11-09 01:17:14,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1673253766] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:17:14,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1436987123] [2024-11-09 01:17:14,858 INFO L159 IcfgInterpreter]: Started Sifa with 34 locations of interest [2024-11-09 01:17:14,858 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:17:14,858 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:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:426) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:312) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:273) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) 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) [2024-11-09 01:17:14,859 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:17:14,859 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2024-11-09 01:17:14,859 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [152355852] [2024-11-09 01:17:14,859 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 01:17:14,860 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 01:17:14,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:17:14,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 01:17:14,861 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=718, Unknown=4, NotChecked=0, Total=812 [2024-11-09 01:17:14,861 INFO L87 Difference]: Start difference. First operand 205 states and 264 transitions. Second operand has 19 states, 16 states have (on average 1.9375) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 01:17:26,174 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.05s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:17:29,100 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:17:31,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:17:31,600 INFO L93 Difference]: Finished difference Result 302 states and 387 transitions. [2024-11-09 01:17:31,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-09 01:17:31,601 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.9375) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) Word has length 48 [2024-11-09 01:17:31,602 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:17:31,607 INFO L225 Difference]: With dead ends: 302 [2024-11-09 01:17:31,607 INFO L226 Difference]: Without dead ends: 300 [2024-11-09 01:17:31,608 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 42 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 375 ImplicationChecksByTransitivity, 25.0s TimeCoverageRelationStatistics Valid=279, Invalid=1697, Unknown=4, NotChecked=0, Total=1980 [2024-11-09 01:17:31,609 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 89 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 641 mSolverCounterSat, 62 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 711 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 641 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:17:31,611 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 229 Invalid, 711 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 641 Invalid, 8 Unknown, 0 Unchecked, 12.1s Time] [2024-11-09 01:17:31,612 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2024-11-09 01:17:31,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 265. [2024-11-09 01:17:31,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 265 states, 161 states have (on average 1.1490683229813665) internal successors, (185), 173 states have internal predecessors, (185), 58 states have call successors, (58), 35 states have call predecessors, (58), 45 states have return successors, (95), 60 states have call predecessors, (95), 54 states have call successors, (95) [2024-11-09 01:17:31,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 265 states to 265 states and 338 transitions. [2024-11-09 01:17:31,724 INFO L78 Accepts]: Start accepts. Automaton has 265 states and 338 transitions. Word has length 48 [2024-11-09 01:17:31,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:17:31,725 INFO L471 AbstractCegarLoop]: Abstraction has 265 states and 338 transitions. [2024-11-09 01:17:31,725 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 1.9375) internal successors, (31), 15 states have internal predecessors, (31), 8 states have call successors, (10), 7 states have call predecessors, (10), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-09 01:17:31,725 INFO L276 IsEmpty]: Start isEmpty. Operand 265 states and 338 transitions. [2024-11-09 01:17:31,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-09 01:17:31,727 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:17:31,727 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:17:31,736 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-09 01:17:31,928 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:31,928 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:17:31,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:17:31,929 INFO L85 PathProgramCache]: Analyzing trace with hash -438687373, now seen corresponding path program 1 times [2024-11-09 01:17:31,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:17:31,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1290315137] [2024-11-09 01:17:31,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:31,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:17:32,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:17:33,636 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 01:17:33,637 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:17:33,637 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1290315137] [2024-11-09 01:17:33,637 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1290315137] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:17:33,637 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:17:33,637 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2024-11-09 01:17:33,638 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2144171142] [2024-11-09 01:17:33,638 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:17:33,638 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 01:17:33,638 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:17:33,639 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 01:17:33,639 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2024-11-09 01:17:33,640 INFO L87 Difference]: Start difference. First operand 265 states and 338 transitions. Second operand has 15 states, 10 states have (on average 2.6) internal successors, (26), 13 states have internal predecessors, (26), 7 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 01:17:34,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:17:34,985 INFO L93 Difference]: Finished difference Result 446 states and 571 transitions. [2024-11-09 01:17:34,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 01:17:34,986 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 10 states have (on average 2.6) internal successors, (26), 13 states have internal predecessors, (26), 7 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) Word has length 50 [2024-11-09 01:17:34,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:17:34,989 INFO L225 Difference]: With dead ends: 446 [2024-11-09 01:17:34,989 INFO L226 Difference]: Without dead ends: 238 [2024-11-09 01:17:34,992 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=76, Invalid=430, Unknown=0, NotChecked=0, Total=506 [2024-11-09 01:17:34,993 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 18 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 490 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 504 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 490 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-11-09 01:17:34,993 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 124 Invalid, 504 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 490 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-11-09 01:17:34,994 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2024-11-09 01:17:35,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 201. [2024-11-09 01:17:35,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 201 states, 125 states have (on average 1.128) internal successors, (141), 133 states have internal predecessors, (141), 41 states have call successors, (41), 28 states have call predecessors, (41), 34 states have return successors, (59), 40 states have call predecessors, (59), 38 states have call successors, (59) [2024-11-09 01:17:35,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 201 states to 201 states and 241 transitions. [2024-11-09 01:17:35,108 INFO L78 Accepts]: Start accepts. Automaton has 201 states and 241 transitions. Word has length 50 [2024-11-09 01:17:35,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:17:35,108 INFO L471 AbstractCegarLoop]: Abstraction has 201 states and 241 transitions. [2024-11-09 01:17:35,108 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 10 states have (on average 2.6) internal successors, (26), 13 states have internal predecessors, (26), 7 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 01:17:35,109 INFO L276 IsEmpty]: Start isEmpty. Operand 201 states and 241 transitions. [2024-11-09 01:17:35,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-09 01:17:35,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:17:35,110 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:17:35,110 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-09 01:17:35,111 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:17:35,111 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:17:35,111 INFO L85 PathProgramCache]: Analyzing trace with hash 1169705389, now seen corresponding path program 1 times [2024-11-09 01:17:35,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:17:35,111 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1320584254] [2024-11-09 01:17:35,111 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:35,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:17:35,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:17:35,186 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [154914963] [2024-11-09 01:17:35,190 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:17:35,191 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:17:35,191 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:17:35,193 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:17:35,195 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 01:17:35,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:17:35,548 WARN L253 TraceCheckSpWp]: Trace formula consists of 353 conjuncts, 179 conjuncts are in the unsatisfiable core [2024-11-09 01:17:35,555 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:17:35,577 INFO L349 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2024-11-09 01:17:35,577 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 34 [2024-11-09 01:17:35,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-09 01:17:36,157 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:17:36,159 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:17:36,163 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 101 treesize of output 48 [2024-11-09 01:17:47,138 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 01:17:47,145 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 135 treesize of output 78 [2024-11-09 01:17:48,287 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 153 treesize of output 77 [2024-11-09 01:17:49,343 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 16 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-09 01:17:49,343 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:18:09,514 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:18:09,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1320584254] [2024-11-09 01:18:09,515 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:18:09,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [154914963] [2024-11-09 01:18:09,515 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [154914963] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:18:09,515 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1529144452] [2024-11-09 01:18:09,518 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2024-11-09 01:18:09,518 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:18:09,518 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:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:426) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:312) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:273) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) 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) [2024-11-09 01:18:09,519 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 01:18:09,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2024-11-09 01:18:09,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1516310726] [2024-11-09 01:18:09,519 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 01:18:09,520 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-09 01:18:09,520 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:18:09,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-09 01:18:09,521 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=1078, Unknown=12, NotChecked=0, Total=1190 [2024-11-09 01:18:09,521 INFO L87 Difference]: Start difference. First operand 201 states and 241 transitions. Second operand has 26 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 19 states have internal predecessors, (30), 9 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 01:18:11,592 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:18,788 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:25,584 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:27,638 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:28,874 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.13s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:30,671 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.71s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:32,780 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.10s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:34,994 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.04s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:36,533 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.53s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:38,886 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:40,983 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:43,336 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:47,571 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:49,640 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:18:59,410 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:08,813 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:19:10,950 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:13,386 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:15,427 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:17,280 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.78s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:18,904 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.53s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:20,217 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:19:22,232 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:24,553 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:26,496 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.86s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:28,502 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:30,584 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:32,627 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:35,307 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:36,997 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.64s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:39,050 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:41,097 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:44,190 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.90s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:46,409 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.82s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:47,945 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.48s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:49,406 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.46s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:50,961 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.55s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:52,981 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.96s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:54,890 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.91s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:56,903 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:58,945 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-11-09 01:19:58,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:19:58,954 INFO L93 Difference]: Finished difference Result 320 states and 394 transitions. [2024-11-09 01:19:58,955 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-09 01:19:58,955 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 19 states have internal predecessors, (30), 9 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 50 [2024-11-09 01:19:58,956 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:19:58,958 INFO L225 Difference]: With dead ends: 320 [2024-11-09 01:19:58,958 INFO L226 Difference]: Without dead ends: 316 [2024-11-09 01:19:58,959 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 527 ImplicationChecksByTransitivity, 55.0s TimeCoverageRelationStatistics Valid=240, Invalid=2492, Unknown=24, NotChecked=0, Total=2756 [2024-11-09 01:19:58,959 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 100 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 1127 mSolverCounterSat, 55 mSolverCounterUnsat, 56 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 83.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 323 SdHoareTripleChecker+Invalid, 1238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 1127 IncrementalHoareTripleChecker+Invalid, 56 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 84.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:19:58,960 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [104 Valid, 323 Invalid, 1238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 1127 Invalid, 56 Unknown, 0 Unchecked, 84.1s Time] [2024-11-09 01:19:58,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 316 states. [2024-11-09 01:19:59,048 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 316 to 254. [2024-11-09 01:19:59,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 254 states, 157 states have (on average 1.1337579617834395) internal successors, (178), 167 states have internal predecessors, (178), 51 states have call successors, (51), 34 states have call predecessors, (51), 45 states have return successors, (82), 52 states have call predecessors, (82), 47 states have call successors, (82) [2024-11-09 01:19:59,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 254 states to 254 states and 311 transitions. [2024-11-09 01:19:59,051 INFO L78 Accepts]: Start accepts. Automaton has 254 states and 311 transitions. Word has length 50 [2024-11-09 01:19:59,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:19:59,051 INFO L471 AbstractCegarLoop]: Abstraction has 254 states and 311 transitions. [2024-11-09 01:19:59,052 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 18 states have (on average 1.6666666666666667) internal successors, (30), 19 states have internal predecessors, (30), 9 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 01:19:59,052 INFO L276 IsEmpty]: Start isEmpty. Operand 254 states and 311 transitions. [2024-11-09 01:19:59,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-09 01:19:59,053 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:19:59,053 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:19:59,069 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 01:19:59,253 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:19:59,254 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:19:59,254 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:19:59,254 INFO L85 PathProgramCache]: Analyzing trace with hash 327335823, now seen corresponding path program 3 times [2024-11-09 01:19:59,254 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:19:59,254 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [259041972] [2024-11-09 01:19:59,254 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:19:59,254 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:19:59,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:19:59,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [876457212] [2024-11-09 01:19:59,389 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 01:19:59,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:19:59,389 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:19:59,391 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:19:59,394 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_1ecde816-ad9a-4f4b-906d-a2aeb8a79a5b/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 01:20:08,581 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 01:20:08,581 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:20:08,589 WARN L253 TraceCheckSpWp]: Trace formula consists of 354 conjuncts, 310 conjuncts are in the unsatisfiable core [2024-11-09 01:20:08,597 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:20:10,625 INFO L349 Elim1Store]: treesize reduction 429, result has 33.0 percent of original size [2024-11-09 01:20:10,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 9 case distinctions, treesize of input 396 treesize of output 375