./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 839c364b Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 3bef4637cc296c755ba815d09f028f51f0bde7e0d2e6155f2b5c648b5201a193 --- Real Ultimate output --- This is Ultimate 0.2.2-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 17:07:19,818 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 17:07:19,819 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 17:07:19,845 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 17:07:19,846 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 17:07:19,848 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 17:07:19,849 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 17:07:19,851 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 17:07:19,852 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 17:07:19,855 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 17:07:19,856 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 17:07:19,857 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 17:07:19,857 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 17:07:19,859 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 17:07:19,860 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 17:07:19,864 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 17:07:19,865 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 17:07:19,866 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 17:07:19,867 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 17:07:19,871 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 17:07:19,872 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 17:07:19,873 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 17:07:19,874 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 17:07:19,874 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 17:07:19,879 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 17:07:19,879 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 17:07:19,879 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 17:07:19,880 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 17:07:19,881 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 17:07:19,881 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 17:07:19,882 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 17:07:19,882 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 17:07:19,883 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 17:07:19,884 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 17:07:19,885 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 17:07:19,885 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 17:07:19,885 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 17:07:19,886 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 17:07:19,886 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 17:07:19,886 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 17:07:19,888 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 17:07:19,888 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2021-12-14 17:07:19,907 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 17:07:19,911 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 17:07:19,911 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 17:07:19,911 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 17:07:19,912 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-14 17:07:19,912 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-14 17:07:19,913 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 17:07:19,913 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 17:07:19,913 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 17:07:19,913 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 17:07:19,914 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 17:07:19,914 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 17:07:19,914 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-14 17:07:19,914 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-14 17:07:19,914 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-14 17:07:19,915 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-14 17:07:19,915 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 17:07:19,915 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-14 17:07:19,916 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-14 17:07:19,917 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 17:07:19,917 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 3bef4637cc296c755ba815d09f028f51f0bde7e0d2e6155f2b5c648b5201a193 [2021-12-14 17:07:20,088 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 17:07:20,114 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 17:07:20,116 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 17:07:20,117 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 17:07:20,117 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 17:07:20,118 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i [2021-12-14 17:07:20,158 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e8f4dc6c6/5849acc2396d468a8d551ffe802dca15/FLAG90be285f6 [2021-12-14 17:07:20,605 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 17:07:20,605 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i [2021-12-14 17:07:20,647 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e8f4dc6c6/5849acc2396d468a8d551ffe802dca15/FLAG90be285f6 [2021-12-14 17:07:20,884 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e8f4dc6c6/5849acc2396d468a8d551ffe802dca15 [2021-12-14 17:07:20,886 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 17:07:20,887 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 17:07:20,892 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 17:07:20,893 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 17:07:20,896 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 17:07:20,897 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 05:07:20" (1/1) ... [2021-12-14 17:07:20,899 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@70b1f642 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:20, skipping insertion in model container [2021-12-14 17:07:20,899 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 05:07:20" (1/1) ... [2021-12-14 17:07:20,903 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 17:07:20,965 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 17:07:21,161 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i[4496,4509] [2021-12-14 17:07:21,166 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i[4556,4569] [2021-12-14 17:07:21,573 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,576 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,577 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,578 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,579 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,590 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,599 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,600 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,602 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,604 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,606 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,606 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,607 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,796 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-14 17:07:21,797 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-14 17:07:21,797 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-14 17:07:21,798 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-14 17:07:21,799 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-14 17:07:21,799 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-14 17:07:21,800 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-14 17:07:21,800 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-14 17:07:21,801 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-14 17:07:21,804 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-14 17:07:21,878 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-14 17:07:21,900 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 17:07:21,914 INFO L203 MainTranslator]: Completed pre-run [2021-12-14 17:07:21,930 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i[4496,4509] [2021-12-14 17:07:21,931 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/aws-c-common/aws_linked_list_rbegin_harness.i[4556,4569] [2021-12-14 17:07:21,962 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,962 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,962 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,963 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,963 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,966 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,966 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,967 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,967 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,969 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,969 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,970 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:21,970 WARN L1533 CHandler]: Possible shadowing of function index [2021-12-14 17:07:22,025 WARN L610 FunctionHandler]: implicit declaration of function __atomic_load_n [2021-12-14 17:07:22,026 WARN L610 FunctionHandler]: implicit declaration of function __atomic_store_n [2021-12-14 17:07:22,026 WARN L610 FunctionHandler]: implicit declaration of function __atomic_exchange_n [2021-12-14 17:07:22,026 WARN L610 FunctionHandler]: implicit declaration of function __atomic_compare_exchange_n [2021-12-14 17:07:22,030 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_add [2021-12-14 17:07:22,030 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_sub [2021-12-14 17:07:22,030 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_or [2021-12-14 17:07:22,031 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_and [2021-12-14 17:07:22,031 WARN L610 FunctionHandler]: implicit declaration of function __atomic_fetch_xor [2021-12-14 17:07:22,031 WARN L610 FunctionHandler]: implicit declaration of function __atomic_thread_fence [2021-12-14 17:07:22,053 WARN L610 FunctionHandler]: implicit declaration of function __builtin_va_copy [2021-12-14 17:07:22,063 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 17:07:22,188 INFO L208 MainTranslator]: Completed translation [2021-12-14 17:07:22,189 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22 WrapperNode [2021-12-14 17:07:22,189 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 17:07:22,190 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-14 17:07:22,190 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-14 17:07:22,190 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-14 17:07:22,194 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,272 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,297 INFO L137 Inliner]: procedures = 679, calls = 1041, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 142 [2021-12-14 17:07:22,297 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-14 17:07:22,298 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-14 17:07:22,298 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-14 17:07:22,298 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-14 17:07:22,304 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,304 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,307 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,307 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,316 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,319 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,321 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,324 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-14 17:07:22,324 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-14 17:07:22,324 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-14 17:07:22,325 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-14 17:07:22,325 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (1/1) ... [2021-12-14 17:07:22,348 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 17:07:22,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:22,376 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-12-14 17:07:22,396 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-12-14 17:07:22,405 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-14 17:07:22,406 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-14 17:07:22,406 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-14 17:07:22,406 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2021-12-14 17:07:22,406 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2021-12-14 17:07:22,407 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-14 17:07:22,407 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2021-12-14 17:07:22,408 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2021-12-14 17:07:22,408 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-14 17:07:22,408 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-14 17:07:22,408 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-14 17:07:22,408 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-14 17:07:22,408 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-14 17:07:22,409 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-14 17:07:22,409 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-14 17:07:22,409 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-14 17:07:22,409 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-12-14 17:07:22,409 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2021-12-14 17:07:22,409 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2021-12-14 17:07:22,409 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-14 17:07:22,597 INFO L236 CfgBuilder]: Building ICFG [2021-12-14 17:07:22,598 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-14 17:07:22,744 INFO L277 CfgBuilder]: Performing block encoding [2021-12-14 17:07:22,749 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-14 17:07:22,749 INFO L301 CfgBuilder]: Removed 2 assume(true) statements. [2021-12-14 17:07:22,750 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 05:07:22 BoogieIcfgContainer [2021-12-14 17:07:22,751 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-14 17:07:22,752 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-14 17:07:22,752 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-14 17:07:22,754 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-14 17:07:22,754 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.12 05:07:20" (1/3) ... [2021-12-14 17:07:22,755 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b5b15cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 05:07:22, skipping insertion in model container [2021-12-14 17:07:22,755 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 05:07:22" (2/3) ... [2021-12-14 17:07:22,755 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4b5b15cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 05:07:22, skipping insertion in model container [2021-12-14 17:07:22,756 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 05:07:22" (3/3) ... [2021-12-14 17:07:22,756 INFO L111 eAbstractionObserver]: Analyzing ICFG aws_linked_list_rbegin_harness.i [2021-12-14 17:07:22,760 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-14 17:07:22,760 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-14 17:07:22,789 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-14 17:07:22,810 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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, mLoopAccelerationTechnique=FAST_UPR [2021-12-14 17:07:22,811 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-14 17:07:22,822 INFO L276 IsEmpty]: Start isEmpty. Operand has 69 states, 49 states have (on average 1.346938775510204) internal successors, (66), 50 states have internal predecessors, (66), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-14 17:07:22,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2021-12-14 17:07:22,829 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:22,830 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2021-12-14 17:07:22,830 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:22,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:22,834 INFO L85 PathProgramCache]: Analyzing trace with hash -1062572114, now seen corresponding path program 1 times [2021-12-14 17:07:22,840 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:22,840 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [167999453] [2021-12-14 17:07:22,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:22,841 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:22,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,084 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:23,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,097 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:23,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,108 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:23,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,127 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-14 17:07:23,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,136 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-14 17:07:23,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,169 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2021-12-14 17:07:23,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,181 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2021-12-14 17:07:23,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,213 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2021-12-14 17:07:23,214 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:23,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [167999453] [2021-12-14 17:07:23,217 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [167999453] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:23,217 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 17:07:23,217 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-14 17:07:23,219 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [655715967] [2021-12-14 17:07:23,220 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:23,224 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-14 17:07:23,224 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:23,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-14 17:07:23,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-14 17:07:23,250 INFO L87 Difference]: Start difference. First operand has 69 states, 49 states have (on average 1.346938775510204) internal successors, (66), 50 states have internal predecessors, (66), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 13.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:23,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:23,273 INFO L93 Difference]: Finished difference Result 130 states and 186 transitions. [2021-12-14 17:07:23,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-14 17:07:23,275 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 13.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 68 [2021-12-14 17:07:23,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:23,281 INFO L225 Difference]: With dead ends: 130 [2021-12-14 17:07:23,281 INFO L226 Difference]: Without dead ends: 64 [2021-12-14 17:07:23,284 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-14 17:07:23,286 INFO L933 BasicCegarLoop]: 88 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:23,287 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 17:07:23,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2021-12-14 17:07:23,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2021-12-14 17:07:23,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 45 states have (on average 1.288888888888889) internal successors, (58), 46 states have internal predecessors, (58), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2021-12-14 17:07:23,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 83 transitions. [2021-12-14 17:07:23,321 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 83 transitions. Word has length 68 [2021-12-14 17:07:23,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:23,321 INFO L470 AbstractCegarLoop]: Abstraction has 64 states and 83 transitions. [2021-12-14 17:07:23,321 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 13.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:23,322 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 83 transitions. [2021-12-14 17:07:23,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2021-12-14 17:07:23,324 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:23,324 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2021-12-14 17:07:23,324 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-14 17:07:23,324 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:23,325 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:23,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1946087212, now seen corresponding path program 1 times [2021-12-14 17:07:23,325 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:23,325 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1301329897] [2021-12-14 17:07:23,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:23,326 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:23,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,423 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:23,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,464 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:23,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,484 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:23,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,508 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-14 17:07:23,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,547 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-14 17:07:23,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,558 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2021-12-14 17:07:23,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,566 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2021-12-14 17:07:23,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,591 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 3 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2021-12-14 17:07:23,592 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:23,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1301329897] [2021-12-14 17:07:23,592 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1301329897] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:23,592 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [870411540] [2021-12-14 17:07:23,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:23,593 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:23,593 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:23,594 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:23,620 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-14 17:07:23,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:23,790 INFO L263 TraceCheckSpWp]: Trace formula consists of 345 conjuncts, 64 conjunts are in the unsatisfiable core [2021-12-14 17:07:23,800 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:23,947 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:23,952 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 19 [2021-12-14 17:07:23,966 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:23,967 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 19 [2021-12-14 17:07:24,037 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,038 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,039 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,040 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 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 26 treesize of output 29 [2021-12-14 17:07:24,048 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,048 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,049 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:24,050 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 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 26 treesize of output 29 [2021-12-14 17:07:24,581 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 37 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 17:07:24,581 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:24,582 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [870411540] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:24,582 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:24,582 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [6] total 14 [2021-12-14 17:07:24,583 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [808579501] [2021-12-14 17:07:24,583 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:24,583 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 17:07:24,583 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:24,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 17:07:24,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2021-12-14 17:07:24,584 INFO L87 Difference]: Start difference. First operand 64 states and 83 transitions. Second operand has 10 states, 9 states have (on average 5.111111111111111) internal successors, (46), 10 states have internal predecessors, (46), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-14 17:07:24,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:24,628 INFO L93 Difference]: Finished difference Result 136 states and 180 transitions. [2021-12-14 17:07:24,629 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-12-14 17:07:24,629 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 5.111111111111111) internal successors, (46), 10 states have internal predecessors, (46), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) Word has length 68 [2021-12-14 17:07:24,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:24,631 INFO L225 Difference]: With dead ends: 136 [2021-12-14 17:07:24,631 INFO L226 Difference]: Without dead ends: 89 [2021-12-14 17:07:24,632 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 70 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2021-12-14 17:07:24,632 INFO L933 BasicCegarLoop]: 78 mSDtfsCounter, 17 mSDsluCounter, 322 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 67 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:24,633 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 400 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 67 Unchecked, 0.0s Time] [2021-12-14 17:07:24,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2021-12-14 17:07:24,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2021-12-14 17:07:24,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 64 states have (on average 1.3125) internal successors, (84), 67 states have internal predecessors, (84), 16 states have call successors, (16), 7 states have call predecessors, (16), 8 states have return successors, (18), 14 states have call predecessors, (18), 15 states have call successors, (18) [2021-12-14 17:07:24,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 118 transitions. [2021-12-14 17:07:24,642 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 118 transitions. Word has length 68 [2021-12-14 17:07:24,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:24,642 INFO L470 AbstractCegarLoop]: Abstraction has 89 states and 118 transitions. [2021-12-14 17:07:24,643 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 5.111111111111111) internal successors, (46), 10 states have internal predecessors, (46), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-14 17:07:24,643 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 118 transitions. [2021-12-14 17:07:24,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2021-12-14 17:07:24,644 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:24,644 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2021-12-14 17:07:24,680 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2021-12-14 17:07:24,883 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:24,883 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:24,883 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:24,884 INFO L85 PathProgramCache]: Analyzing trace with hash 2008126826, now seen corresponding path program 1 times [2021-12-14 17:07:24,884 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:24,884 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325685115] [2021-12-14 17:07:24,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:24,884 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:24,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:24,971 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:24,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:24,977 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:24,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:24,983 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:24,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:24,998 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2021-12-14 17:07:25,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:25,020 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-14 17:07:25,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:25,030 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2021-12-14 17:07:25,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:25,036 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2021-12-14 17:07:25,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:25,045 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 3 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2021-12-14 17:07:25,046 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:25,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325685115] [2021-12-14 17:07:25,046 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1325685115] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:25,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1083720354] [2021-12-14 17:07:25,046 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:25,046 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:25,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:25,047 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:25,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-14 17:07:25,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:25,156 INFO L263 TraceCheckSpWp]: Trace formula consists of 340 conjuncts, 53 conjunts are in the unsatisfiable core [2021-12-14 17:07:25,159 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:25,245 INFO L354 Elim1Store]: treesize reduction 30, result has 38.8 percent of original size [2021-12-14 17:07:25,264 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 55 [2021-12-14 17:07:25,275 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:25,276 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:25,280 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 10 treesize of output 9 [2021-12-14 17:07:25,285 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 10 treesize of output 9 [2021-12-14 17:07:25,344 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2021-12-14 17:07:25,359 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2021-12-14 17:07:25,362 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-12-14 17:07:25,596 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-14 17:07:25,598 INFO L354 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2021-12-14 17:07:25,599 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 22 [2021-12-14 17:07:25,894 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 34 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 17:07:25,894 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:07:26,373 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-14 17:07:26,373 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 118 treesize of output 120 [2021-12-14 17:07:26,378 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 144 treesize of output 136 [2021-12-14 17:07:26,386 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 138 treesize of output 126 [2021-12-14 17:07:26,393 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 63 [2021-12-14 17:07:26,400 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 126 treesize of output 118 [2021-12-14 17:07:26,406 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 118 treesize of output 102 [2021-12-14 17:07:26,443 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-12-14 17:07:26,479 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 24 [2021-12-14 17:07:26,574 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-14 17:07:26,574 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1083720354] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:07:26,574 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:07:26,574 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 17, 15] total 33 [2021-12-14 17:07:26,575 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813905938] [2021-12-14 17:07:26,575 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:07:26,575 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2021-12-14 17:07:26,576 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:26,576 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2021-12-14 17:07:26,576 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=949, Unknown=0, NotChecked=0, Total=1056 [2021-12-14 17:07:26,577 INFO L87 Difference]: Start difference. First operand 89 states and 118 transitions. Second operand has 33 states, 30 states have (on average 3.3666666666666667) internal successors, (101), 29 states have internal predecessors, (101), 10 states have call successors, (18), 4 states have call predecessors, (18), 9 states have return successors, (17), 6 states have call predecessors, (17), 10 states have call successors, (17) [2021-12-14 17:07:27,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:27,604 INFO L93 Difference]: Finished difference Result 298 states and 449 transitions. [2021-12-14 17:07:27,605 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2021-12-14 17:07:27,605 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 3.3666666666666667) internal successors, (101), 29 states have internal predecessors, (101), 10 states have call successors, (18), 4 states have call predecessors, (18), 9 states have return successors, (17), 6 states have call predecessors, (17), 10 states have call successors, (17) Word has length 68 [2021-12-14 17:07:27,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:27,609 INFO L225 Difference]: With dead ends: 298 [2021-12-14 17:07:27,609 INFO L226 Difference]: Without dead ends: 201 [2021-12-14 17:07:27,610 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 122 SyntacticMatches, 3 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 724 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=289, Invalid=2903, Unknown=0, NotChecked=0, Total=3192 [2021-12-14 17:07:27,611 INFO L933 BasicCegarLoop]: 146 mSDtfsCounter, 259 mSDsluCounter, 2153 mSDsCounter, 0 mSdLazyCounter, 881 mSolverCounterSat, 155 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 262 SdHoareTripleChecker+Valid, 2299 SdHoareTripleChecker+Invalid, 1451 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 155 IncrementalHoareTripleChecker+Valid, 881 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 415 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:27,611 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [262 Valid, 2299 Invalid, 1451 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [155 Valid, 881 Invalid, 0 Unknown, 415 Unchecked, 0.5s Time] [2021-12-14 17:07:27,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2021-12-14 17:07:27,628 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 177. [2021-12-14 17:07:27,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 137 states have (on average 1.3795620437956204) internal successors, (189), 144 states have internal predecessors, (189), 25 states have call successors, (25), 9 states have call predecessors, (25), 14 states have return successors, (49), 23 states have call predecessors, (49), 24 states have call successors, (49) [2021-12-14 17:07:27,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 263 transitions. [2021-12-14 17:07:27,631 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 263 transitions. Word has length 68 [2021-12-14 17:07:27,631 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:27,631 INFO L470 AbstractCegarLoop]: Abstraction has 177 states and 263 transitions. [2021-12-14 17:07:27,631 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 3.3666666666666667) internal successors, (101), 29 states have internal predecessors, (101), 10 states have call successors, (18), 4 states have call predecessors, (18), 9 states have return successors, (17), 6 states have call predecessors, (17), 10 states have call successors, (17) [2021-12-14 17:07:27,632 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 263 transitions. [2021-12-14 17:07:27,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2021-12-14 17:07:27,634 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:27,634 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2021-12-14 17:07:27,654 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:27,835 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-12-14 17:07:27,836 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:27,836 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:27,836 INFO L85 PathProgramCache]: Analyzing trace with hash -1195332088, now seen corresponding path program 1 times [2021-12-14 17:07:27,836 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:27,836 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1294894738] [2021-12-14 17:07:27,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:27,836 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:27,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,869 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:27,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,875 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:27,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,882 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:27,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2021-12-14 17:07:27,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,911 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-14 17:07:27,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,917 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2021-12-14 17:07:27,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,922 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2021-12-14 17:07:27,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:27,930 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2021-12-14 17:07:27,930 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:27,930 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1294894738] [2021-12-14 17:07:27,930 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1294894738] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:27,931 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [482611248] [2021-12-14 17:07:27,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:27,931 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:27,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:27,932 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:27,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-14 17:07:28,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,057 INFO L263 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 17:07:28,059 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:28,193 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-14 17:07:28,193 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:28,194 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [482611248] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:28,194 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:28,194 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [6] total 11 [2021-12-14 17:07:28,194 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751571878] [2021-12-14 17:07:28,194 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:28,194 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 17:07:28,195 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:28,195 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 17:07:28,195 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2021-12-14 17:07:28,195 INFO L87 Difference]: Start difference. First operand 177 states and 263 transitions. Second operand has 7 states, 7 states have (on average 6.0) internal successors, (42), 7 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:28,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:28,328 INFO L93 Difference]: Finished difference Result 318 states and 481 transitions. [2021-12-14 17:07:28,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-14 17:07:28,329 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 6.0) internal successors, (42), 7 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 70 [2021-12-14 17:07:28,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:28,330 INFO L225 Difference]: With dead ends: 318 [2021-12-14 17:07:28,330 INFO L226 Difference]: Without dead ends: 193 [2021-12-14 17:07:28,331 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2021-12-14 17:07:28,332 INFO L933 BasicCegarLoop]: 58 mSDtfsCounter, 107 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 245 SdHoareTripleChecker+Invalid, 148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:28,332 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [107 Valid, 245 Invalid, 148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 17:07:28,333 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2021-12-14 17:07:28,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 184. [2021-12-14 17:07:28,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 184 states, 142 states have (on average 1.352112676056338) internal successors, (192), 151 states have internal predecessors, (192), 25 states have call successors, (25), 9 states have call predecessors, (25), 16 states have return successors, (55), 23 states have call predecessors, (55), 24 states have call successors, (55) [2021-12-14 17:07:28,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 184 states to 184 states and 272 transitions. [2021-12-14 17:07:28,346 INFO L78 Accepts]: Start accepts. Automaton has 184 states and 272 transitions. Word has length 70 [2021-12-14 17:07:28,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:28,347 INFO L470 AbstractCegarLoop]: Abstraction has 184 states and 272 transitions. [2021-12-14 17:07:28,347 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 6.0) internal successors, (42), 7 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:28,347 INFO L276 IsEmpty]: Start isEmpty. Operand 184 states and 272 transitions. [2021-12-14 17:07:28,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2021-12-14 17:07:28,350 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:28,350 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1] [2021-12-14 17:07:28,369 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:28,567 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:28,567 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:28,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:28,568 INFO L85 PathProgramCache]: Analyzing trace with hash -316025515, now seen corresponding path program 1 times [2021-12-14 17:07:28,568 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:28,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1087197547] [2021-12-14 17:07:28,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:28,568 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:28,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,604 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:28,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,609 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:28,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,616 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:28,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,645 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2021-12-14 17:07:28,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,651 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2021-12-14 17:07:28,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,657 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2021-12-14 17:07:28,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,662 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2021-12-14 17:07:28,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,673 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2021-12-14 17:07:28,673 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:28,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1087197547] [2021-12-14 17:07:28,673 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1087197547] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:28,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [814366261] [2021-12-14 17:07:28,673 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:28,674 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:28,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:28,675 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:28,676 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-14 17:07:28,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:28,797 INFO L263 TraceCheckSpWp]: Trace formula consists of 366 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-14 17:07:28,799 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:28,952 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-14 17:07:28,952 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:28,953 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [814366261] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:28,953 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:28,953 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [7] total 13 [2021-12-14 17:07:28,953 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1172908606] [2021-12-14 17:07:28,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:28,954 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-14 17:07:28,954 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:28,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-14 17:07:28,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2021-12-14 17:07:28,955 INFO L87 Difference]: Start difference. First operand 184 states and 272 transitions. Second operand has 8 states, 8 states have (on average 5.5) internal successors, (44), 8 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:29,155 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:29,156 INFO L93 Difference]: Finished difference Result 351 states and 531 transitions. [2021-12-14 17:07:29,156 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-14 17:07:29,156 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.5) internal successors, (44), 8 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 72 [2021-12-14 17:07:29,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:29,158 INFO L225 Difference]: With dead ends: 351 [2021-12-14 17:07:29,158 INFO L226 Difference]: Without dead ends: 217 [2021-12-14 17:07:29,159 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2021-12-14 17:07:29,159 INFO L933 BasicCegarLoop]: 57 mSDtfsCounter, 144 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 291 SdHoareTripleChecker+Invalid, 214 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:29,159 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [144 Valid, 291 Invalid, 214 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 17:07:29,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2021-12-14 17:07:29,170 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 188. [2021-12-14 17:07:29,171 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 146 states have (on average 1.3356164383561644) internal successors, (195), 155 states have internal predecessors, (195), 25 states have call successors, (25), 9 states have call predecessors, (25), 16 states have return successors, (55), 23 states have call predecessors, (55), 24 states have call successors, (55) [2021-12-14 17:07:29,172 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 275 transitions. [2021-12-14 17:07:29,172 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 275 transitions. Word has length 72 [2021-12-14 17:07:29,172 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:29,172 INFO L470 AbstractCegarLoop]: Abstraction has 188 states and 275 transitions. [2021-12-14 17:07:29,173 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.5) internal successors, (44), 8 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:29,173 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 275 transitions. [2021-12-14 17:07:29,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2021-12-14 17:07:29,175 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:29,175 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1] [2021-12-14 17:07:29,194 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:29,394 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:29,395 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:29,395 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:29,395 INFO L85 PathProgramCache]: Analyzing trace with hash -1928092350, now seen corresponding path program 1 times [2021-12-14 17:07:29,395 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:29,395 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [452646427] [2021-12-14 17:07:29,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:29,396 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:29,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,426 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:29,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,432 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:29,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,438 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:29,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,451 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2021-12-14 17:07:29,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,456 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2021-12-14 17:07:29,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,463 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2021-12-14 17:07:29,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,468 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2021-12-14 17:07:29,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,474 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2021-12-14 17:07:29,475 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:29,475 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [452646427] [2021-12-14 17:07:29,475 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [452646427] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:29,475 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1495025642] [2021-12-14 17:07:29,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:29,475 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:29,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:29,476 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:29,478 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-14 17:07:29,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,582 INFO L263 TraceCheckSpWp]: Trace formula consists of 369 conjuncts, 2 conjunts are in the unsatisfiable core [2021-12-14 17:07:29,583 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:29,669 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 26 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2021-12-14 17:07:29,670 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:29,670 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1495025642] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:29,670 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:29,670 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [4] total 5 [2021-12-14 17:07:29,670 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1782176857] [2021-12-14 17:07:29,670 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:29,671 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-14 17:07:29,671 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:29,671 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-14 17:07:29,671 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-14 17:07:29,671 INFO L87 Difference]: Start difference. First operand 188 states and 275 transitions. Second operand has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:29,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:29,684 INFO L93 Difference]: Finished difference Result 296 states and 441 transitions. [2021-12-14 17:07:29,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-14 17:07:29,685 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 73 [2021-12-14 17:07:29,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:29,686 INFO L225 Difference]: With dead ends: 296 [2021-12-14 17:07:29,686 INFO L226 Difference]: Without dead ends: 151 [2021-12-14 17:07:29,687 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-14 17:07:29,687 INFO L933 BasicCegarLoop]: 85 mSDtfsCounter, 6 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:29,688 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 163 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 17:07:29,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2021-12-14 17:07:29,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 113. [2021-12-14 17:07:29,693 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 88 states have (on average 1.3409090909090908) internal successors, (118), 91 states have internal predecessors, (118), 16 states have call successors, (16), 7 states have call predecessors, (16), 8 states have return successors, (22), 14 states have call predecessors, (22), 15 states have call successors, (22) [2021-12-14 17:07:29,694 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 156 transitions. [2021-12-14 17:07:29,694 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 156 transitions. Word has length 73 [2021-12-14 17:07:29,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:29,695 INFO L470 AbstractCegarLoop]: Abstraction has 113 states and 156 transitions. [2021-12-14 17:07:29,695 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-14 17:07:29,695 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 156 transitions. [2021-12-14 17:07:29,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2021-12-14 17:07:29,696 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:29,696 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:29,716 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:29,913 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:29,914 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:29,914 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:29,914 INFO L85 PathProgramCache]: Analyzing trace with hash 137287748, now seen corresponding path program 1 times [2021-12-14 17:07:29,914 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:29,914 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [226143409] [2021-12-14 17:07:29,914 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:29,914 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:29,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,948 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:29,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,953 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:29,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,958 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:29,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,976 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:29,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:29,982 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2021-12-14 17:07:29,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:30,002 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2021-12-14 17:07:30,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:30,009 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2021-12-14 17:07:30,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:30,014 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2021-12-14 17:07:30,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:30,020 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 3 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2021-12-14 17:07:30,021 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:30,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [226143409] [2021-12-14 17:07:30,021 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [226143409] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:30,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1450837981] [2021-12-14 17:07:30,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:30,021 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:30,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:30,022 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:30,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-14 17:07:30,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:30,170 INFO L263 TraceCheckSpWp]: Trace formula consists of 399 conjuncts, 51 conjunts are in the unsatisfiable core [2021-12-14 17:07:30,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:30,224 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,227 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 19 [2021-12-14 17:07:30,232 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,233 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 19 [2021-12-14 17:07:30,293 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,294 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,294 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,295 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 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 26 treesize of output 29 [2021-12-14 17:07:30,299 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,300 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,300 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:30,301 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 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 28 treesize of output 31 [2021-12-14 17:07:31,698 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-12-14 17:07:31,699 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:31,699 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1450837981] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:31,699 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:31,699 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [7] total 15 [2021-12-14 17:07:31,699 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1221333014] [2021-12-14 17:07:31,699 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:31,699 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 17:07:31,700 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:31,700 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 17:07:31,700 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=177, Unknown=0, NotChecked=0, Total=210 [2021-12-14 17:07:31,700 INFO L87 Difference]: Start difference. First operand 113 states and 156 transitions. Second operand has 10 states, 10 states have (on average 5.2) internal successors, (52), 10 states have internal predecessors, (52), 5 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 5 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 17:07:31,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:31,775 INFO L93 Difference]: Finished difference Result 251 states and 354 transitions. [2021-12-14 17:07:31,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-14 17:07:31,776 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 5.2) internal successors, (52), 10 states have internal predecessors, (52), 5 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 5 states have call predecessors, (8), 4 states have call successors, (8) Word has length 81 [2021-12-14 17:07:31,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:31,777 INFO L225 Difference]: With dead ends: 251 [2021-12-14 17:07:31,777 INFO L226 Difference]: Without dead ends: 194 [2021-12-14 17:07:31,777 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 82 SyntacticMatches, 8 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2021-12-14 17:07:31,778 INFO L933 BasicCegarLoop]: 98 mSDtfsCounter, 27 mSDsluCounter, 517 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 615 SdHoareTripleChecker+Invalid, 148 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 120 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:31,778 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [36 Valid, 615 Invalid, 148 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 120 Unchecked, 0.0s Time] [2021-12-14 17:07:31,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 194 states. [2021-12-14 17:07:31,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 194 to 173. [2021-12-14 17:07:31,785 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 135 states have (on average 1.3555555555555556) internal successors, (183), 141 states have internal predecessors, (183), 23 states have call successors, (23), 10 states have call predecessors, (23), 14 states have return successors, (35), 21 states have call predecessors, (35), 22 states have call successors, (35) [2021-12-14 17:07:31,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 241 transitions. [2021-12-14 17:07:31,786 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 241 transitions. Word has length 81 [2021-12-14 17:07:31,787 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:31,787 INFO L470 AbstractCegarLoop]: Abstraction has 173 states and 241 transitions. [2021-12-14 17:07:31,787 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 5.2) internal successors, (52), 10 states have internal predecessors, (52), 5 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 5 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 17:07:31,787 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 241 transitions. [2021-12-14 17:07:31,788 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2021-12-14 17:07:31,788 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:31,788 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:31,806 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:32,003 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:32,003 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:32,004 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:32,004 INFO L85 PathProgramCache]: Analyzing trace with hash -672058878, now seen corresponding path program 1 times [2021-12-14 17:07:32,004 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:32,004 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1581074529] [2021-12-14 17:07:32,004 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:32,004 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:32,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,052 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:32,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,056 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:32,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,063 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:32,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,086 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:32,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,092 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2021-12-14 17:07:32,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,116 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2021-12-14 17:07:32,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,124 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2021-12-14 17:07:32,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,128 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2021-12-14 17:07:32,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,137 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 3 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2021-12-14 17:07:32,137 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:32,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1581074529] [2021-12-14 17:07:32,137 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1581074529] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:32,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [403150894] [2021-12-14 17:07:32,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:32,138 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:32,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:32,160 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:32,223 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-14 17:07:32,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:32,311 INFO L263 TraceCheckSpWp]: Trace formula consists of 394 conjuncts, 53 conjunts are in the unsatisfiable core [2021-12-14 17:07:32,315 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:32,406 INFO L354 Elim1Store]: treesize reduction 30, result has 38.8 percent of original size [2021-12-14 17:07:32,407 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 55 [2021-12-14 17:07:32,417 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:32,418 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:32,422 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 10 treesize of output 9 [2021-12-14 17:07:32,426 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 10 treesize of output 9 [2021-12-14 17:07:32,569 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2021-12-14 17:07:32,936 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-14 17:07:32,940 INFO L354 Elim1Store]: treesize reduction 17, result has 15.0 percent of original size [2021-12-14 17:07:32,940 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 36 treesize of output 25 [2021-12-14 17:07:33,192 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 18 proven. 26 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-14 17:07:33,193 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:07:33,724 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-14 17:07:33,724 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 118 treesize of output 120 [2021-12-14 17:07:33,728 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 144 treesize of output 136 [2021-12-14 17:07:33,732 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 63 [2021-12-14 17:07:33,743 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 64 treesize of output 58 [2021-12-14 17:07:33,750 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 54 [2021-12-14 17:07:33,755 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 46 [2021-12-14 17:07:33,846 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:33,916 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 20 proven. 10 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-14 17:07:33,916 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [403150894] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:07:33,916 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:07:33,916 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 17, 15] total 34 [2021-12-14 17:07:33,916 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [424139399] [2021-12-14 17:07:33,916 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:07:33,917 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2021-12-14 17:07:33,917 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:33,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2021-12-14 17:07:33,918 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1013, Unknown=0, NotChecked=0, Total=1122 [2021-12-14 17:07:33,918 INFO L87 Difference]: Start difference. First operand 173 states and 241 transitions. Second operand has 34 states, 31 states have (on average 4.096774193548387) internal successors, (127), 33 states have internal predecessors, (127), 11 states have call successors, (22), 4 states have call predecessors, (22), 9 states have return successors, (21), 9 states have call predecessors, (21), 11 states have call successors, (21) [2021-12-14 17:07:35,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:35,182 INFO L93 Difference]: Finished difference Result 514 states and 768 transitions. [2021-12-14 17:07:35,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2021-12-14 17:07:35,183 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 31 states have (on average 4.096774193548387) internal successors, (127), 33 states have internal predecessors, (127), 11 states have call successors, (22), 4 states have call predecessors, (22), 9 states have return successors, (21), 9 states have call predecessors, (21), 11 states have call successors, (21) Word has length 81 [2021-12-14 17:07:35,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:35,185 INFO L225 Difference]: With dead ends: 514 [2021-12-14 17:07:35,186 INFO L226 Difference]: Without dead ends: 352 [2021-12-14 17:07:35,187 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 150 SyntacticMatches, 7 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1040 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=363, Invalid=4059, Unknown=0, NotChecked=0, Total=4422 [2021-12-14 17:07:35,187 INFO L933 BasicCegarLoop]: 155 mSDtfsCounter, 314 mSDsluCounter, 2663 mSDsCounter, 0 mSdLazyCounter, 1274 mSolverCounterSat, 91 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 330 SdHoareTripleChecker+Valid, 2818 SdHoareTripleChecker+Invalid, 2112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 1274 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 747 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:35,188 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [330 Valid, 2818 Invalid, 2112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 1274 Invalid, 0 Unknown, 747 Unchecked, 0.7s Time] [2021-12-14 17:07:35,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 352 states. [2021-12-14 17:07:35,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 352 to 228. [2021-12-14 17:07:35,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 228 states, 184 states have (on average 1.3532608695652173) internal successors, (249), 193 states have internal predecessors, (249), 23 states have call successors, (23), 14 states have call predecessors, (23), 20 states have return successors, (46), 20 states have call predecessors, (46), 22 states have call successors, (46) [2021-12-14 17:07:35,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 228 states to 228 states and 318 transitions. [2021-12-14 17:07:35,217 INFO L78 Accepts]: Start accepts. Automaton has 228 states and 318 transitions. Word has length 81 [2021-12-14 17:07:35,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:35,217 INFO L470 AbstractCegarLoop]: Abstraction has 228 states and 318 transitions. [2021-12-14 17:07:35,218 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 31 states have (on average 4.096774193548387) internal successors, (127), 33 states have internal predecessors, (127), 11 states have call successors, (22), 4 states have call predecessors, (22), 9 states have return successors, (21), 9 states have call predecessors, (21), 11 states have call successors, (21) [2021-12-14 17:07:35,218 INFO L276 IsEmpty]: Start isEmpty. Operand 228 states and 318 transitions. [2021-12-14 17:07:35,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2021-12-14 17:07:35,219 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:35,219 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:35,239 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:35,423 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:35,424 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:35,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:35,424 INFO L85 PathProgramCache]: Analyzing trace with hash 431382673, now seen corresponding path program 1 times [2021-12-14 17:07:35,424 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:35,424 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1119671427] [2021-12-14 17:07:35,425 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:35,425 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:35,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,468 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:35,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,473 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:35,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,478 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:35,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,553 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:35,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,567 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2021-12-14 17:07:35,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,575 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2021-12-14 17:07:35,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,583 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2021-12-14 17:07:35,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,588 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2021-12-14 17:07:35,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,596 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-14 17:07:35,596 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:35,597 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1119671427] [2021-12-14 17:07:35,597 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1119671427] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:35,597 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1962958503] [2021-12-14 17:07:35,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:35,597 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:35,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:35,598 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:35,599 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-14 17:07:35,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:35,724 INFO L263 TraceCheckSpWp]: Trace formula consists of 406 conjuncts, 43 conjunts are in the unsatisfiable core [2021-12-14 17:07:35,729 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:35,781 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:35,781 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:35,791 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:35,792 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:36,695 WARN L860 $PredicateComparison]: unable to prove that (or (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| Int) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| Int)) (not (= (select (select |c_#memory_$Pointer$.base| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|) 0))) (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| Int) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| Int)) (not (= (select (select |c_#memory_$Pointer$.offset| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|) 0)))) is different from true [2021-12-14 17:07:36,829 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 26 proven. 1 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2021-12-14 17:07:36,830 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:07:36,968 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-14 17:07:36,969 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1962958503] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:07:36,969 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:07:36,969 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 12, 8] total 18 [2021-12-14 17:07:36,969 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [162033815] [2021-12-14 17:07:36,969 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:07:36,970 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-12-14 17:07:36,970 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:36,970 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-14 17:07:36,970 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=228, Unknown=1, NotChecked=30, Total=306 [2021-12-14 17:07:36,971 INFO L87 Difference]: Start difference. First operand 228 states and 318 transitions. Second operand has 18 states, 18 states have (on average 4.833333333333333) internal successors, (87), 18 states have internal predecessors, (87), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 5 states have call predecessors, (16), 6 states have call successors, (16) [2021-12-14 17:07:37,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:37,336 INFO L93 Difference]: Finished difference Result 721 states and 1104 transitions. [2021-12-14 17:07:37,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-12-14 17:07:37,337 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.833333333333333) internal successors, (87), 18 states have internal predecessors, (87), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 5 states have call predecessors, (16), 6 states have call successors, (16) Word has length 83 [2021-12-14 17:07:37,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:37,339 INFO L225 Difference]: With dead ends: 721 [2021-12-14 17:07:37,339 INFO L226 Difference]: Without dead ends: 562 [2021-12-14 17:07:37,340 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 177 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=110, Invalid=445, Unknown=1, NotChecked=44, Total=600 [2021-12-14 17:07:37,340 INFO L933 BasicCegarLoop]: 79 mSDtfsCounter, 215 mSDsluCounter, 532 mSDsCounter, 0 mSdLazyCounter, 444 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 244 SdHoareTripleChecker+Valid, 611 SdHoareTripleChecker+Invalid, 653 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 444 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 181 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:37,340 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [244 Valid, 611 Invalid, 653 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 444 Invalid, 0 Unknown, 181 Unchecked, 0.2s Time] [2021-12-14 17:07:37,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 562 states. [2021-12-14 17:07:37,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 562 to 328. [2021-12-14 17:07:37,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 328 states, 273 states have (on average 1.358974358974359) internal successors, (371), 283 states have internal predecessors, (371), 30 states have call successors, (30), 18 states have call predecessors, (30), 24 states have return successors, (60), 26 states have call predecessors, (60), 29 states have call successors, (60) [2021-12-14 17:07:37,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 328 states to 328 states and 461 transitions. [2021-12-14 17:07:37,357 INFO L78 Accepts]: Start accepts. Automaton has 328 states and 461 transitions. Word has length 83 [2021-12-14 17:07:37,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:37,357 INFO L470 AbstractCegarLoop]: Abstraction has 328 states and 461 transitions. [2021-12-14 17:07:37,358 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.833333333333333) internal successors, (87), 18 states have internal predecessors, (87), 6 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 5 states have call predecessors, (16), 6 states have call successors, (16) [2021-12-14 17:07:37,358 INFO L276 IsEmpty]: Start isEmpty. Operand 328 states and 461 transitions. [2021-12-14 17:07:37,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2021-12-14 17:07:37,359 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:37,359 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:37,376 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:37,574 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2021-12-14 17:07:37,575 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:37,575 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:37,575 INFO L85 PathProgramCache]: Analyzing trace with hash 13986067, now seen corresponding path program 1 times [2021-12-14 17:07:37,575 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:37,575 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [272344670] [2021-12-14 17:07:37,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:37,575 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:37,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,597 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:37,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,600 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:37,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,604 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:37,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,619 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:37,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,626 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2021-12-14 17:07:37,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,629 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2021-12-14 17:07:37,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,634 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2021-12-14 17:07:37,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,638 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2021-12-14 17:07:37,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,643 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2021-12-14 17:07:37,643 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:37,643 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [272344670] [2021-12-14 17:07:37,643 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [272344670] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:37,643 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [235042021] [2021-12-14 17:07:37,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:37,643 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:37,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:37,672 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:37,673 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-14 17:07:37,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:37,791 INFO L263 TraceCheckSpWp]: Trace formula consists of 401 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 17:07:37,792 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:37,918 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-12-14 17:07:37,918 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:37,918 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [235042021] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:37,918 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:37,919 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2021-12-14 17:07:37,919 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1323988705] [2021-12-14 17:07:37,919 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:37,919 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 17:07:37,919 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:37,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 17:07:37,920 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 17:07:37,920 INFO L87 Difference]: Start difference. First operand 328 states and 461 transitions. Second operand has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-14 17:07:37,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:37,946 INFO L93 Difference]: Finished difference Result 553 states and 799 transitions. [2021-12-14 17:07:37,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 17:07:37,947 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 83 [2021-12-14 17:07:37,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:37,948 INFO L225 Difference]: With dead ends: 553 [2021-12-14 17:07:37,948 INFO L226 Difference]: Without dead ends: 302 [2021-12-14 17:07:37,949 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-14 17:07:37,950 INFO L933 BasicCegarLoop]: 91 mSDtfsCounter, 8 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:37,950 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 247 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 17:07:37,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 302 states. [2021-12-14 17:07:37,961 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 302 to 295. [2021-12-14 17:07:37,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 295 states, 242 states have (on average 1.334710743801653) internal successors, (323), 252 states have internal predecessors, (323), 29 states have call successors, (29), 17 states have call predecessors, (29), 23 states have return successors, (58), 25 states have call predecessors, (58), 28 states have call successors, (58) [2021-12-14 17:07:37,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 295 states to 295 states and 410 transitions. [2021-12-14 17:07:37,963 INFO L78 Accepts]: Start accepts. Automaton has 295 states and 410 transitions. Word has length 83 [2021-12-14 17:07:37,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:37,964 INFO L470 AbstractCegarLoop]: Abstraction has 295 states and 410 transitions. [2021-12-14 17:07:37,964 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 12.5) internal successors, (50), 4 states have internal predecessors, (50), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-14 17:07:37,964 INFO L276 IsEmpty]: Start isEmpty. Operand 295 states and 410 transitions. [2021-12-14 17:07:37,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2021-12-14 17:07:37,965 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:37,965 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:38,006 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:38,180 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-12-14 17:07:38,180 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:38,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:38,181 INFO L85 PathProgramCache]: Analyzing trace with hash 1975560725, now seen corresponding path program 1 times [2021-12-14 17:07:38,181 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:38,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [870644088] [2021-12-14 17:07:38,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:38,181 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:38,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,284 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:38,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,290 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:38,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,297 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:38,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,314 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:38,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,319 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2021-12-14 17:07:38,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,323 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 49 [2021-12-14 17:07:38,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,329 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2021-12-14 17:07:38,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,332 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2021-12-14 17:07:38,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,337 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2021-12-14 17:07:38,338 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:38,338 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [870644088] [2021-12-14 17:07:38,338 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [870644088] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:38,338 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1693422615] [2021-12-14 17:07:38,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:38,338 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:38,338 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:38,339 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:38,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-14 17:07:38,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 396 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 17:07:38,465 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:38,557 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2021-12-14 17:07:38,557 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:38,557 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1693422615] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:38,557 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:38,558 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [7] total 7 [2021-12-14 17:07:38,558 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1331772252] [2021-12-14 17:07:38,558 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:38,558 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 17:07:38,558 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:38,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 17:07:38,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-14 17:07:38,559 INFO L87 Difference]: Start difference. First operand 295 states and 410 transitions. Second operand has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-14 17:07:38,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:38,578 INFO L93 Difference]: Finished difference Result 481 states and 679 transitions. [2021-12-14 17:07:38,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 17:07:38,578 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 83 [2021-12-14 17:07:38,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:38,579 INFO L225 Difference]: With dead ends: 481 [2021-12-14 17:07:38,579 INFO L226 Difference]: Without dead ends: 216 [2021-12-14 17:07:38,580 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-12-14 17:07:38,580 INFO L933 BasicCegarLoop]: 82 mSDtfsCounter, 2 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:38,581 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 237 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 17:07:38,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2021-12-14 17:07:38,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 194. [2021-12-14 17:07:38,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 194 states, 155 states have (on average 1.238709677419355) internal successors, (192), 161 states have internal predecessors, (192), 21 states have call successors, (21), 14 states have call predecessors, (21), 17 states have return successors, (31), 18 states have call predecessors, (31), 20 states have call successors, (31) [2021-12-14 17:07:38,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 194 states to 194 states and 244 transitions. [2021-12-14 17:07:38,588 INFO L78 Accepts]: Start accepts. Automaton has 194 states and 244 transitions. Word has length 83 [2021-12-14 17:07:38,588 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:38,588 INFO L470 AbstractCegarLoop]: Abstraction has 194 states and 244 transitions. [2021-12-14 17:07:38,588 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 13.0) internal successors, (52), 4 states have internal predecessors, (52), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2021-12-14 17:07:38,588 INFO L276 IsEmpty]: Start isEmpty. Operand 194 states and 244 transitions. [2021-12-14 17:07:38,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2021-12-14 17:07:38,589 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:38,589 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:38,608 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:38,803 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-14 17:07:38,803 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:38,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:38,804 INFO L85 PathProgramCache]: Analyzing trace with hash -233275002, now seen corresponding path program 1 times [2021-12-14 17:07:38,804 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:38,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1946508971] [2021-12-14 17:07:38,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:38,804 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:38,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,841 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:38,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,845 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:38,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,849 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:38,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,855 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:38,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,859 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2021-12-14 17:07:38,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,862 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2021-12-14 17:07:38,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,877 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2021-12-14 17:07:38,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,896 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 68 [2021-12-14 17:07:38,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:38,902 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2021-12-14 17:07:38,902 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:38,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1946508971] [2021-12-14 17:07:38,903 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1946508971] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:38,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1419199997] [2021-12-14 17:07:38,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:38,903 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:38,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:38,920 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:38,962 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-14 17:07:39,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:39,072 INFO L263 TraceCheckSpWp]: Trace formula consists of 409 conjuncts, 48 conjunts are in the unsatisfiable core [2021-12-14 17:07:39,074 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:39,124 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:39,125 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:39,135 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-14 17:07:39,138 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 case distinctions, treesize of input 9 treesize of output 15 [2021-12-14 17:07:39,772 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 28 proven. 12 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2021-12-14 17:07:39,772 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:07:40,205 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 10 proven. 20 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-12-14 17:07:40,205 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1419199997] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:07:40,205 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:07:40,205 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 14, 10] total 25 [2021-12-14 17:07:40,205 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [330361055] [2021-12-14 17:07:40,205 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:07:40,205 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2021-12-14 17:07:40,205 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:40,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-12-14 17:07:40,206 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2021-12-14 17:07:40,206 INFO L87 Difference]: Start difference. First operand 194 states and 244 transitions. Second operand has 25 states, 24 states have (on average 5.041666666666667) internal successors, (121), 22 states have internal predecessors, (121), 10 states have call successors, (22), 4 states have call predecessors, (22), 8 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) [2021-12-14 17:07:40,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:40,618 INFO L93 Difference]: Finished difference Result 297 states and 373 transitions. [2021-12-14 17:07:40,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2021-12-14 17:07:40,619 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 5.041666666666667) internal successors, (121), 22 states have internal predecessors, (121), 10 states have call successors, (22), 4 states have call predecessors, (22), 8 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) Word has length 84 [2021-12-14 17:07:40,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:40,620 INFO L225 Difference]: With dead ends: 297 [2021-12-14 17:07:40,620 INFO L226 Difference]: Without dead ends: 189 [2021-12-14 17:07:40,621 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 164 SyntacticMatches, 7 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 340 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=228, Invalid=1494, Unknown=0, NotChecked=0, Total=1722 [2021-12-14 17:07:40,621 INFO L933 BasicCegarLoop]: 71 mSDtfsCounter, 110 mSDsluCounter, 696 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 767 SdHoareTripleChecker+Invalid, 414 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 55 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:40,621 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [116 Valid, 767 Invalid, 414 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 328 Invalid, 0 Unknown, 55 Unchecked, 0.2s Time] [2021-12-14 17:07:40,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2021-12-14 17:07:40,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 186. [2021-12-14 17:07:40,627 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 148 states have (on average 1.2162162162162162) internal successors, (180), 153 states have internal predecessors, (180), 21 states have call successors, (21), 14 states have call predecessors, (21), 16 states have return successors, (28), 18 states have call predecessors, (28), 20 states have call successors, (28) [2021-12-14 17:07:40,628 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 229 transitions. [2021-12-14 17:07:40,628 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 229 transitions. Word has length 84 [2021-12-14 17:07:40,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:40,628 INFO L470 AbstractCegarLoop]: Abstraction has 186 states and 229 transitions. [2021-12-14 17:07:40,629 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 5.041666666666667) internal successors, (121), 22 states have internal predecessors, (121), 10 states have call successors, (22), 4 states have call predecessors, (22), 8 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) [2021-12-14 17:07:40,629 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 229 transitions. [2021-12-14 17:07:40,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2021-12-14 17:07:40,629 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:40,629 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 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, 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] [2021-12-14 17:07:40,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:40,846 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-14 17:07:40,847 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:40,847 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:40,847 INFO L85 PathProgramCache]: Analyzing trace with hash -413998114, now seen corresponding path program 1 times [2021-12-14 17:07:40,847 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:40,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [438225362] [2021-12-14 17:07:40,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:40,848 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:40,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,901 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:40,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:40,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,910 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:40,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,920 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:40,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,925 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2021-12-14 17:07:40,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,930 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2021-12-14 17:07:40,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,953 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2021-12-14 17:07:40,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,958 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2021-12-14 17:07:40,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:40,963 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-14 17:07:40,964 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:40,964 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [438225362] [2021-12-14 17:07:40,964 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [438225362] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:40,964 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1081311140] [2021-12-14 17:07:40,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:40,964 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:40,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:40,980 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:40,981 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-14 17:07:41,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,113 INFO L263 TraceCheckSpWp]: Trace formula consists of 413 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-14 17:07:41,115 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:41,287 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2021-12-14 17:07:41,287 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 17:07:41,288 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1081311140] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 17:07:41,288 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-14 17:07:41,288 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [7] total 13 [2021-12-14 17:07:41,288 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [225567439] [2021-12-14 17:07:41,288 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 17:07:41,288 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-14 17:07:41,289 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:41,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-14 17:07:41,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2021-12-14 17:07:41,289 INFO L87 Difference]: Start difference. First operand 186 states and 229 transitions. Second operand has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 17:07:41,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:41,402 INFO L93 Difference]: Finished difference Result 248 states and 306 transitions. [2021-12-14 17:07:41,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 17:07:41,403 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 86 [2021-12-14 17:07:41,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:41,404 INFO L225 Difference]: With dead ends: 248 [2021-12-14 17:07:41,404 INFO L226 Difference]: Without dead ends: 158 [2021-12-14 17:07:41,404 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=247, Unknown=0, NotChecked=0, Total=306 [2021-12-14 17:07:41,404 INFO L933 BasicCegarLoop]: 59 mSDtfsCounter, 106 mSDsluCounter, 241 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 172 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:41,405 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [106 Valid, 300 Invalid, 172 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 17:07:41,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2021-12-14 17:07:41,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 156. [2021-12-14 17:07:41,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 125 states have (on average 1.216) internal successors, (152), 127 states have internal predecessors, (152), 19 states have call successors, (19), 12 states have call predecessors, (19), 11 states have return successors, (20), 16 states have call predecessors, (20), 18 states have call successors, (20) [2021-12-14 17:07:41,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 191 transitions. [2021-12-14 17:07:41,410 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 191 transitions. Word has length 86 [2021-12-14 17:07:41,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:41,410 INFO L470 AbstractCegarLoop]: Abstraction has 156 states and 191 transitions. [2021-12-14 17:07:41,410 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 17:07:41,410 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 191 transitions. [2021-12-14 17:07:41,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2021-12-14 17:07:41,411 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:41,411 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:41,449 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:41,629 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-14 17:07:41,630 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:41,630 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:41,630 INFO L85 PathProgramCache]: Analyzing trace with hash -806881120, now seen corresponding path program 1 times [2021-12-14 17:07:41,630 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:41,631 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [923757414] [2021-12-14 17:07:41,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:41,631 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:41,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,679 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:41,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,683 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:41,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,690 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 17:07:41,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,697 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:41,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,709 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2021-12-14 17:07:41,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,714 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 50 [2021-12-14 17:07:41,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,731 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:41,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,735 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 75 [2021-12-14 17:07:41,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,753 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 81 [2021-12-14 17:07:41,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,759 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2021-12-14 17:07:41,759 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:41,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [923757414] [2021-12-14 17:07:41,759 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [923757414] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:41,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1337767251] [2021-12-14 17:07:41,760 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:41,760 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:41,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:41,761 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:41,762 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-14 17:07:41,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:41,902 INFO L263 TraceCheckSpWp]: Trace formula consists of 458 conjuncts, 29 conjunts are in the unsatisfiable core [2021-12-14 17:07:41,904 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:42,092 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 31 proven. 3 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-14 17:07:42,092 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:07:42,311 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2021-12-14 17:07:42,311 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1337767251] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:07:42,311 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:07:42,311 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 13, 7] total 18 [2021-12-14 17:07:42,311 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [447623566] [2021-12-14 17:07:42,312 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:07:42,312 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-12-14 17:07:42,312 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:07:42,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-14 17:07:42,312 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=267, Unknown=0, NotChecked=0, Total=306 [2021-12-14 17:07:42,312 INFO L87 Difference]: Start difference. First operand 156 states and 191 transitions. Second operand has 18 states, 15 states have (on average 4.8) internal successors, (72), 14 states have internal predecessors, (72), 5 states have call successors, (12), 2 states have call predecessors, (12), 8 states have return successors, (15), 6 states have call predecessors, (15), 5 states have call successors, (15) [2021-12-14 17:07:42,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 17:07:42,417 INFO L93 Difference]: Finished difference Result 233 states and 291 transitions. [2021-12-14 17:07:42,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-14 17:07:42,418 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 15 states have (on average 4.8) internal successors, (72), 14 states have internal predecessors, (72), 5 states have call successors, (12), 2 states have call predecessors, (12), 8 states have return successors, (15), 6 states have call predecessors, (15), 5 states have call successors, (15) Word has length 97 [2021-12-14 17:07:42,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 17:07:42,419 INFO L225 Difference]: With dead ends: 233 [2021-12-14 17:07:42,419 INFO L226 Difference]: Without dead ends: 170 [2021-12-14 17:07:42,419 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 200 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=61, Invalid=401, Unknown=0, NotChecked=0, Total=462 [2021-12-14 17:07:42,419 INFO L933 BasicCegarLoop]: 80 mSDtfsCounter, 15 mSDsluCounter, 924 mSDsCounter, 0 mSdLazyCounter, 161 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 1004 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 161 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 17:07:42,420 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 1004 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 161 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 17:07:42,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 170 states. [2021-12-14 17:07:42,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 170 to 127. [2021-12-14 17:07:42,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 100 states have (on average 1.22) internal successors, (122), 101 states have internal predecessors, (122), 17 states have call successors, (17), 10 states have call predecessors, (17), 9 states have return successors, (17), 15 states have call predecessors, (17), 16 states have call successors, (17) [2021-12-14 17:07:42,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 156 transitions. [2021-12-14 17:07:42,426 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 156 transitions. Word has length 97 [2021-12-14 17:07:42,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 17:07:42,426 INFO L470 AbstractCegarLoop]: Abstraction has 127 states and 156 transitions. [2021-12-14 17:07:42,426 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 15 states have (on average 4.8) internal successors, (72), 14 states have internal predecessors, (72), 5 states have call successors, (12), 2 states have call predecessors, (12), 8 states have return successors, (15), 6 states have call predecessors, (15), 5 states have call successors, (15) [2021-12-14 17:07:42,426 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 156 transitions. [2021-12-14 17:07:42,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2021-12-14 17:07:42,427 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 17:07:42,427 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 17:07:42,447 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-12-14 17:07:42,645 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-12-14 17:07:42,645 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 17:07:42,645 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 17:07:42,645 INFO L85 PathProgramCache]: Analyzing trace with hash 1617876444, now seen corresponding path program 1 times [2021-12-14 17:07:42,645 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 17:07:42,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [40308513] [2021-12-14 17:07:42,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:42,646 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 17:07:42,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,767 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-14 17:07:42,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,772 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 17:07:42,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,778 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-14 17:07:42,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,846 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:42,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,853 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2021-12-14 17:07:42,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,858 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2021-12-14 17:07:42,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,871 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-14 17:07:42,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,876 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 80 [2021-12-14 17:07:42,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,880 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 86 [2021-12-14 17:07:42,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:42,890 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2021-12-14 17:07:42,890 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 17:07:42,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [40308513] [2021-12-14 17:07:42,891 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [40308513] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 17:07:42,891 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [737263508] [2021-12-14 17:07:42,891 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 17:07:42,891 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 17:07:42,891 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 17:07:42,908 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 17:07:42,951 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-12-14 17:07:43,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 17:07:43,117 INFO L263 TraceCheckSpWp]: Trace formula consists of 523 conjuncts, 60 conjunts are in the unsatisfiable core [2021-12-14 17:07:43,146 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 17:07:43,242 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 14 [2021-12-14 17:07:43,245 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:43,246 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2021-12-14 17:07:43,299 INFO L354 Elim1Store]: treesize reduction 38, result has 22.4 percent of original size [2021-12-14 17:07:43,300 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 66 treesize of output 63 [2021-12-14 17:07:43,303 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:43,304 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 45 [2021-12-14 17:07:43,308 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 16 treesize of output 15 [2021-12-14 17:07:43,315 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 17:07:43,316 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 23 [2021-12-14 17:07:43,318 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-14 17:07:45,344 WARN L860 $PredicateComparison]: unable to prove that (exists ((|v_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.base_BEFORE_CALL_45| Int)) (< (+ (select (select |c_#memory_$Pointer$.base| |v_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.base_BEFORE_CALL_45|) 0) 1) |v_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.base_BEFORE_CALL_45|)) is different from true [2021-12-14 17:08:07,732 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 50 proven. 3 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-12-14 17:08:07,733 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 17:08:08,007 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_1147 (Array Int Int)) (v_ArrVal_1146 (Array Int Int)) (v_ArrVal_1148 Int)) (not (= (select (select (store (store |c_#memory_$Pointer$.base| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| v_ArrVal_1147) |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base| (store (select (store |c_#memory_$Pointer$.base| |c_ULTIMATE.start_ensure_linked_list_is_allocated_~curr~0#1.base| v_ArrVal_1146) |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.base|) (+ |c_ULTIMATE.start_ensure_linked_list_is_allocated_~list#1.offset| 24) v_ArrVal_1148)) |c_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.base|) |c_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.offset|) |c_ULTIMATE.start_aws_linked_list_rbegin_harness_~#list~0#1.base|))) is different from false [2021-12-14 17:08:08,020 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-14 17:08:08,021 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 40 treesize of output 33 [2021-12-14 17:08:08,031 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-14 17:08:08,032 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 144 treesize of output 148 [2021-12-14 17:08:08,036 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 144 treesize of output 140 [2021-12-14 17:08:08,040 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 140 treesize of output 138 [2021-12-14 17:08:08,124 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2021-12-14 17:08:08,137 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 22 [2021-12-14 17:08:08,168 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-14 17:08:08,168 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 55 treesize of output 55 [2021-12-14 17:08:08,293 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 34 trivial. 1 not checked. [2021-12-14 17:08:08,293 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [737263508] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 17:08:08,294 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 17:08:08,294 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13, 11] total 29 [2021-12-14 17:08:08,294 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [659040814] [2021-12-14 17:08:08,294 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 17:08:08,294 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2021-12-14 17:08:08,294 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 17:08:08,294 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2021-12-14 17:08:08,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=618, Unknown=7, NotChecked=102, Total=812 [2021-12-14 17:08:08,295 INFO L87 Difference]: Start difference. First operand 127 states and 156 transitions. Second operand has 29 states, 29 states have (on average 4.9655172413793105) internal successors, (144), 29 states have internal predecessors, (144), 10 states have call successors, (22), 3 states have call predecessors, (22), 5 states have return successors, (21), 8 states have call predecessors, (21), 10 states have call successors, (21)