./Ultimate.py --spec ../sv-benchmarks/c/properties/valid-memcleanup.prp --file ../sv-benchmarks/c/verifythis/tree_del_rec.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for memory safety (memcleanup) 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/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/verifythis/tree_del_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-MemCleanup-32bit-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 valid-memcleanup) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 448d6e9f7f0c094a8335d652a2766ae983308e33ec1a543ceaed97ae79744722 --- Real Ultimate output --- This is Ultimate 0.2.2-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 19:29:47,538 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 19:29:47,540 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 19:29:47,570 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 19:29:47,571 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 19:29:47,573 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 19:29:47,574 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 19:29:47,576 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 19:29:47,578 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 19:29:47,581 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 19:29:47,581 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 19:29:47,582 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 19:29:47,582 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 19:29:47,584 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 19:29:47,585 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 19:29:47,590 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 19:29:47,591 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 19:29:47,592 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 19:29:47,593 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 19:29:47,597 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 19:29:47,598 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 19:29:47,599 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 19:29:47,600 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 19:29:47,601 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 19:29:47,605 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 19:29:47,605 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 19:29:47,606 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 19:29:47,607 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 19:29:47,607 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 19:29:47,608 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 19:29:47,608 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 19:29:47,608 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 19:29:47,609 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 19:29:47,610 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 19:29:47,611 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 19:29:47,612 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 19:29:47,612 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 19:29:47,612 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 19:29:47,612 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 19:29:47,613 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 19:29:47,613 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 19:29:47,614 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-MemCleanup-32bit-Automizer_Default.epf [2021-12-14 19:29:47,641 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 19:29:47,641 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 19:29:47,642 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 19:29:47,642 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 19:29:47,642 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-14 19:29:47,642 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-14 19:29:47,643 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 19:29:47,643 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 19:29:47,643 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 19:29:47,643 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 19:29:47,644 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-14 19:29:47,644 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-14 19:29:47,644 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 19:29:47,644 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-14 19:29:47,645 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 19:29:47,646 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 19:29:47,646 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 19:29:47,646 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-14 19:29:47,646 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 19:29:47,646 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 19:29:47,646 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-14 19:29:47,647 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-14 19:29:47,647 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-14 19:29:47,647 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 19:29:47,648 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 valid-memcleanup) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 448d6e9f7f0c094a8335d652a2766ae983308e33ec1a543ceaed97ae79744722 [2021-12-14 19:29:47,854 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 19:29:47,875 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 19:29:47,877 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 19:29:47,878 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 19:29:47,878 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 19:29:47,879 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/tree_del_rec.c [2021-12-14 19:29:47,918 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5890e20b5/31b2e5aff3684f3fb7504c3f4a391d62/FLAG5053478e1 [2021-12-14 19:29:48,277 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 19:29:48,278 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/tree_del_rec.c [2021-12-14 19:29:48,285 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5890e20b5/31b2e5aff3684f3fb7504c3f4a391d62/FLAG5053478e1 [2021-12-14 19:29:48,294 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5890e20b5/31b2e5aff3684f3fb7504c3f4a391d62 [2021-12-14 19:29:48,296 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 19:29:48,297 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 19:29:48,298 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 19:29:48,298 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 19:29:48,300 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 19:29:48,301 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 07:29:48" (1/1) ... [2021-12-14 19:29:48,302 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5b06147f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:48, skipping insertion in model container [2021-12-14 19:29:48,302 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 07:29:48" (1/1) ... [2021-12-14 19:29:48,306 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 19:29:48,318 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 19:29:48,424 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/verifythis/tree_del_rec.c[585,598] [2021-12-14 19:29:48,433 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:48,435 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:48,447 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 19:29:48,457 ERROR L326 MainTranslator]: Unsupported Syntax: Found a cast between two array/pointer types where the value type is smaller than the cast-to type while using memory model HoenickeLindenmann_Original (while Not using bitvector translation) [2021-12-14 19:29:48,457 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@724c02f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:48, skipping insertion in model container [2021-12-14 19:29:48,457 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 19:29:48,458 INFO L184 ToolchainWalker]: Toolchain execution was canceled (user or tool) before executing de.uni_freiburg.informatik.ultimate.boogie.procedureinliner [2021-12-14 19:29:48,459 INFO L158 Benchmark]: Toolchain (without parser) took 161.27ms. Allocated memory is still 90.2MB. Free memory was 53.2MB in the beginning and 66.2MB in the end (delta: -13.1MB). Peak memory consumption was 5.5MB. Max. memory is 16.1GB. [2021-12-14 19:29:48,460 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 90.2MB. Free memory was 69.9MB in the beginning and 69.9MB in the end (delta: 44.4kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 19:29:48,460 INFO L158 Benchmark]: CACSL2BoogieTranslator took 159.51ms. Allocated memory is still 90.2MB. Free memory was 52.9MB in the beginning and 66.2MB in the end (delta: -13.3MB). Peak memory consumption was 5.5MB. Max. memory is 16.1GB. [2021-12-14 19:29:48,461 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.16ms. Allocated memory is still 90.2MB. Free memory was 69.9MB in the beginning and 69.9MB in the end (delta: 44.4kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 159.51ms. Allocated memory is still 90.2MB. Free memory was 52.9MB in the beginning and 66.2MB in the end (delta: -13.3MB). Peak memory consumption was 5.5MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - UnsupportedSyntaxResult [Line: 28]: Unsupported Syntax Found a cast between two array/pointer types where the value type is smaller than the cast-to type while using memory model HoenickeLindenmann_Original (while Not using bitvector translation) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### 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/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/verifythis/tree_del_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-MemCleanup-32bit-Automizer_Bitvector.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 valid-memcleanup) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 448d6e9f7f0c094a8335d652a2766ae983308e33ec1a543ceaed97ae79744722 --- Real Ultimate output --- This is Ultimate 0.2.2-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 19:29:49,989 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 19:29:49,991 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 19:29:50,008 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 19:29:50,009 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 19:29:50,011 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 19:29:50,014 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 19:29:50,018 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 19:29:50,019 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 19:29:50,023 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 19:29:50,024 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 19:29:50,029 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 19:29:50,030 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 19:29:50,032 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 19:29:50,033 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 19:29:50,037 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 19:29:50,038 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 19:29:50,039 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 19:29:50,042 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 19:29:50,047 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 19:29:50,048 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 19:29:50,049 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 19:29:50,050 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 19:29:50,051 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 19:29:50,056 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 19:29:50,057 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 19:29:50,057 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 19:29:50,058 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 19:29:50,059 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 19:29:50,059 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 19:29:50,060 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 19:29:50,060 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 19:29:50,062 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 19:29:50,062 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 19:29:50,063 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 19:29:50,063 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 19:29:50,064 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 19:29:50,064 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 19:29:50,064 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 19:29:50,065 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 19:29:50,066 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 19:29:50,067 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-MemCleanup-32bit-Automizer_Bitvector.epf [2021-12-14 19:29:50,101 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 19:29:50,102 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 19:29:50,102 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 19:29:50,103 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 19:29:50,104 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-14 19:29:50,104 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-14 19:29:50,105 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 19:29:50,105 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 19:29:50,105 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 19:29:50,106 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 19:29:50,106 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-14 19:29:50,106 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-14 19:29:50,107 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-14 19:29:50,108 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-14 19:29:50,108 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2021-12-14 19:29:50,108 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2021-12-14 19:29:50,108 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-14 19:29:50,108 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 19:29:50,109 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 19:29:50,109 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 19:29:50,109 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-14 19:29:50,109 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 19:29:50,109 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 19:29:50,109 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-14 19:29:50,110 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2021-12-14 19:29:50,110 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2021-12-14 19:29:50,110 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 19:29:50,110 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-12-14 19:29:50,111 INFO L138 SettingsManager]: * Logic for external solver=AUFBV 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 valid-memcleanup) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 448d6e9f7f0c094a8335d652a2766ae983308e33ec1a543ceaed97ae79744722 [2021-12-14 19:29:50,401 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 19:29:50,433 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 19:29:50,435 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 19:29:50,436 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 19:29:50,451 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 19:29:50,452 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/tree_del_rec.c [2021-12-14 19:29:50,505 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b646b2e9/f98369f401904d6198979dbac8528d69/FLAGb107a0d53 [2021-12-14 19:29:50,861 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 19:29:50,861 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/tree_del_rec.c [2021-12-14 19:29:50,867 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b646b2e9/f98369f401904d6198979dbac8528d69/FLAGb107a0d53 [2021-12-14 19:29:51,261 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3b646b2e9/f98369f401904d6198979dbac8528d69 [2021-12-14 19:29:51,273 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 19:29:51,276 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 19:29:51,279 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 19:29:51,279 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 19:29:51,281 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 19:29:51,281 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,282 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1b62d7ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51, skipping insertion in model container [2021-12-14 19:29:51,282 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,287 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 19:29:51,301 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 19:29:51,411 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/verifythis/tree_del_rec.c[585,598] [2021-12-14 19:29:51,426 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,428 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,456 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 19:29:51,482 INFO L200 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2021-12-14 19:29:51,485 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 19:29:51,488 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/verifythis/tree_del_rec.c[585,598] [2021-12-14 19:29:51,491 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,492 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,498 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 19:29:51,502 INFO L203 MainTranslator]: Completed pre-run [2021-12-14 19:29:51,512 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/verifythis/tree_del_rec.c[585,598] [2021-12-14 19:29:51,515 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,516 WARN L1533 CHandler]: Possible shadowing of function min [2021-12-14 19:29:51,522 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 19:29:51,534 INFO L208 MainTranslator]: Completed translation [2021-12-14 19:29:51,534 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51 WrapperNode [2021-12-14 19:29:51,534 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 19:29:51,535 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-14 19:29:51,535 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-14 19:29:51,535 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-14 19:29:51,540 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,548 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,569 INFO L137 Inliner]: procedures = 31, calls = 61, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 75 [2021-12-14 19:29:51,569 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-14 19:29:51,570 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-14 19:29:51,570 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-14 19:29:51,571 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-14 19:29:51,577 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,577 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,592 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,593 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,601 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,613 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,617 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,623 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-14 19:29:51,626 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-14 19:29:51,626 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-14 19:29:51,627 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-14 19:29:51,627 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (1/1) ... [2021-12-14 19:29:51,632 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 19:29:51,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 19:29:51,650 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 19:29:51,687 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 19:29:51,699 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-14 19:29:51,699 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2021-12-14 19:29:51,700 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-14 19:29:51,700 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-14 19:29:51,700 INFO L130 BoogieDeclarations]: Found specification of procedure tree_del [2021-12-14 19:29:51,700 INFO L138 BoogieDeclarations]: Found implementation of procedure tree_del [2021-12-14 19:29:51,700 INFO L130 BoogieDeclarations]: Found specification of procedure min [2021-12-14 19:29:51,700 INFO L138 BoogieDeclarations]: Found implementation of procedure min [2021-12-14 19:29:51,700 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2021-12-14 19:29:51,701 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.meminit [2021-12-14 19:29:51,701 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.meminit [2021-12-14 19:29:51,701 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-14 19:29:51,701 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_tree [2021-12-14 19:29:51,701 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_tree [2021-12-14 19:29:51,701 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-14 19:29:51,701 INFO L130 BoogieDeclarations]: Found specification of procedure size [2021-12-14 19:29:51,701 INFO L138 BoogieDeclarations]: Found implementation of procedure size [2021-12-14 19:29:51,702 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-14 19:29:51,702 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-14 19:29:51,702 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-14 19:29:51,702 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-14 19:29:51,702 INFO L130 BoogieDeclarations]: Found specification of procedure tree_inorder [2021-12-14 19:29:51,702 INFO L138 BoogieDeclarations]: Found implementation of procedure tree_inorder [2021-12-14 19:29:51,702 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-14 19:29:51,702 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE4 [2021-12-14 19:29:51,812 INFO L236 CfgBuilder]: Building ICFG [2021-12-14 19:29:51,813 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-14 19:29:52,291 INFO L277 CfgBuilder]: Performing block encoding [2021-12-14 19:29:52,296 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-14 19:29:52,296 INFO L301 CfgBuilder]: Removed 2 assume(true) statements. [2021-12-14 19:29:52,298 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 07:29:52 BoogieIcfgContainer [2021-12-14 19:29:52,298 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-14 19:29:52,299 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-14 19:29:52,299 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-14 19:29:52,301 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-14 19:29:52,301 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.12 07:29:51" (1/3) ... [2021-12-14 19:29:52,302 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5df663f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 07:29:52, skipping insertion in model container [2021-12-14 19:29:52,302 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 07:29:51" (2/3) ... [2021-12-14 19:29:52,302 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5df663f5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 07:29:52, skipping insertion in model container [2021-12-14 19:29:52,302 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 07:29:52" (3/3) ... [2021-12-14 19:29:52,303 INFO L111 eAbstractionObserver]: Analyzing ICFG tree_del_rec.c [2021-12-14 19:29:52,307 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-14 19:29:52,307 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 55 error locations. [2021-12-14 19:29:52,333 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-14 19:29:52,337 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=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, 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 19:29:52,338 INFO L340 AbstractCegarLoop]: Starting to check reachability of 55 error locations. [2021-12-14 19:29:52,349 INFO L276 IsEmpty]: Start isEmpty. Operand has 174 states, 89 states have (on average 1.7640449438202248) internal successors, (157), 144 states have internal predecessors, (157), 22 states have call successors, (22), 7 states have call predecessors, (22), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-14 19:29:52,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2021-12-14 19:29:52,353 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:52,354 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2021-12-14 19:29:52,354 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting nondet_treeErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:52,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:52,358 INFO L85 PathProgramCache]: Analyzing trace with hash 120433579, now seen corresponding path program 1 times [2021-12-14 19:29:52,365 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:52,365 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [448354797] [2021-12-14 19:29:52,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:52,366 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:52,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:52,368 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:52,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2021-12-14 19:29:52,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:52,418 INFO L263 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-14 19:29:52,420 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:52,474 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 6 treesize of output 5 [2021-12-14 19:29:52,483 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:52,484 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:52,484 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:52,484 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [448354797] [2021-12-14 19:29:52,485 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [448354797] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:52,485 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:52,485 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-14 19:29:52,486 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1325066408] [2021-12-14 19:29:52,487 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:52,490 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-14 19:29:52,490 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:52,517 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-14 19:29:52,518 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 19:29:52,519 INFO L87 Difference]: Start difference. First operand has 174 states, 89 states have (on average 1.7640449438202248) internal successors, (157), 144 states have internal predecessors, (157), 22 states have call successors, (22), 7 states have call predecessors, (22), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-14 19:29:52,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:52,712 INFO L93 Difference]: Finished difference Result 175 states and 200 transitions. [2021-12-14 19:29:52,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-14 19:29:52,714 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2021-12-14 19:29:52,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:52,721 INFO L225 Difference]: With dead ends: 175 [2021-12-14 19:29:52,721 INFO L226 Difference]: Without dead ends: 172 [2021-12-14 19:29:52,722 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 19:29:52,731 INFO L933 BasicCegarLoop]: 197 mSDtfsCounter, 6 mSDsluCounter, 129 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 326 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:52,732 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 326 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-14 19:29:52,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2021-12-14 19:29:52,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 170. [2021-12-14 19:29:52,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 87 states have (on average 1.7011494252873562) internal successors, (148), 140 states have internal predecessors, (148), 22 states have call successors, (22), 7 states have call predecessors, (22), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-14 19:29:52,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 192 transitions. [2021-12-14 19:29:52,799 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 192 transitions. Word has length 5 [2021-12-14 19:29:52,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:52,800 INFO L470 AbstractCegarLoop]: Abstraction has 170 states and 192 transitions. [2021-12-14 19:29:52,800 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-14 19:29:52,800 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 192 transitions. [2021-12-14 19:29:52,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2021-12-14 19:29:52,802 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:52,802 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2021-12-14 19:29:52,824 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Ended with exit code 0 [2021-12-14 19:29:53,008 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:53,008 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting nondet_treeErr1REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:53,009 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:53,009 INFO L85 PathProgramCache]: Analyzing trace with hash 120433580, now seen corresponding path program 1 times [2021-12-14 19:29:53,009 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:53,009 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [432859491] [2021-12-14 19:29:53,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:53,009 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:53,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:53,013 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:53,017 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2021-12-14 19:29:53,048 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:53,049 INFO L263 TraceCheckSpWp]: Trace formula consists of 36 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-14 19:29:53,050 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:53,068 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 6 treesize of output 5 [2021-12-14 19:29:53,081 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:53,082 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:53,082 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:53,082 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [432859491] [2021-12-14 19:29:53,082 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [432859491] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:53,082 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:53,082 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-14 19:29:53,083 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1027520425] [2021-12-14 19:29:53,083 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:53,084 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-14 19:29:53,084 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:53,084 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-14 19:29:53,086 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 19:29:53,086 INFO L87 Difference]: Start difference. First operand 170 states and 192 transitions. Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-14 19:29:53,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:53,269 INFO L93 Difference]: Finished difference Result 169 states and 191 transitions. [2021-12-14 19:29:53,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-14 19:29:53,270 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2021-12-14 19:29:53,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:53,271 INFO L225 Difference]: With dead ends: 169 [2021-12-14 19:29:53,271 INFO L226 Difference]: Without dead ends: 169 [2021-12-14 19:29:53,272 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-14 19:29:53,272 INFO L933 BasicCegarLoop]: 190 mSDtfsCounter, 2 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:53,273 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 327 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-14 19:29:53,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2021-12-14 19:29:53,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2021-12-14 19:29:53,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 169 states, 87 states have (on average 1.6896551724137931) internal successors, (147), 139 states have internal predecessors, (147), 22 states have call successors, (22), 7 states have call predecessors, (22), 7 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2021-12-14 19:29:53,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 191 transitions. [2021-12-14 19:29:53,280 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 191 transitions. Word has length 5 [2021-12-14 19:29:53,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:53,281 INFO L470 AbstractCegarLoop]: Abstraction has 169 states and 191 transitions. [2021-12-14 19:29:53,281 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-14 19:29:53,281 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 191 transitions. [2021-12-14 19:29:53,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-14 19:29:53,282 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:53,282 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:29:53,289 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Forceful destruction successful, exit code 0 [2021-12-14 19:29:53,488 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:53,488 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting minErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:53,489 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:53,489 INFO L85 PathProgramCache]: Analyzing trace with hash 854953177, now seen corresponding path program 1 times [2021-12-14 19:29:53,489 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:53,489 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1681848455] [2021-12-14 19:29:53,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:53,490 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:53,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:53,490 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:53,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2021-12-14 19:29:53,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:53,549 INFO L263 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-14 19:29:53,550 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:53,677 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:53,678 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:53,678 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:53,678 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1681848455] [2021-12-14 19:29:53,678 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1681848455] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:53,678 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:53,678 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-14 19:29:53,679 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1566263038] [2021-12-14 19:29:53,679 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:53,679 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 19:29:53,679 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:53,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 19:29:53,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-14 19:29:53,680 INFO L87 Difference]: Start difference. First operand 169 states and 191 transitions. Second operand has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:53,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:53,788 INFO L93 Difference]: Finished difference Result 233 states and 270 transitions. [2021-12-14 19:29:53,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-14 19:29:53,789 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-14 19:29:53,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:53,790 INFO L225 Difference]: With dead ends: 233 [2021-12-14 19:29:53,791 INFO L226 Difference]: Without dead ends: 233 [2021-12-14 19:29:53,791 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-12-14 19:29:53,791 INFO L933 BasicCegarLoop]: 199 mSDtfsCounter, 91 mSDsluCounter, 957 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 1156 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:53,792 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [91 Valid, 1156 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 19:29:53,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2021-12-14 19:29:53,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 177. [2021-12-14 19:29:53,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 92 states have (on average 1.6521739130434783) internal successors, (152), 145 states have internal predecessors, (152), 23 states have call successors, (23), 8 states have call predecessors, (23), 9 states have return successors, (26), 23 states have call predecessors, (26), 23 states have call successors, (26) [2021-12-14 19:29:53,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 201 transitions. [2021-12-14 19:29:53,801 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 201 transitions. Word has length 11 [2021-12-14 19:29:53,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:53,801 INFO L470 AbstractCegarLoop]: Abstraction has 177 states and 201 transitions. [2021-12-14 19:29:53,801 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 5 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:53,801 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 201 transitions. [2021-12-14 19:29:53,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-14 19:29:53,802 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:53,802 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:29:53,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Forceful destruction successful, exit code 0 [2021-12-14 19:29:54,008 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:54,009 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting nondet_treeErr2REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:54,009 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:54,009 INFO L85 PathProgramCache]: Analyzing trace with hash 873486780, now seen corresponding path program 1 times [2021-12-14 19:29:54,009 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:54,010 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [370507008] [2021-12-14 19:29:54,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:54,010 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:54,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:54,011 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:54,012 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2021-12-14 19:29:54,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:54,086 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-14 19:29:54,087 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:54,104 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 6 treesize of output 5 [2021-12-14 19:29:54,134 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:54,134 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:54,135 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:54,135 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [370507008] [2021-12-14 19:29:54,135 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [370507008] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:54,135 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:54,135 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-14 19:29:54,135 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1672589738] [2021-12-14 19:29:54,135 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:54,136 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 19:29:54,136 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:54,136 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 19:29:54,136 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 19:29:54,137 INFO L87 Difference]: Start difference. First operand 177 states and 201 transitions. Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:54,445 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:54,445 INFO L93 Difference]: Finished difference Result 181 states and 205 transitions. [2021-12-14 19:29:54,448 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-14 19:29:54,449 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-14 19:29:54,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:54,450 INFO L225 Difference]: With dead ends: 181 [2021-12-14 19:29:54,450 INFO L226 Difference]: Without dead ends: 181 [2021-12-14 19:29:54,450 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 19:29:54,450 INFO L933 BasicCegarLoop]: 150 mSDtfsCounter, 89 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 216 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 247 SdHoareTripleChecker+Invalid, 241 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 216 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:54,451 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [95 Valid, 247 Invalid, 241 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 216 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-14 19:29:54,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2021-12-14 19:29:54,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 179. [2021-12-14 19:29:54,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 179 states, 94 states have (on average 1.6595744680851063) internal successors, (156), 145 states have internal predecessors, (156), 23 states have call successors, (23), 8 states have call predecessors, (23), 9 states have return successors, (26), 25 states have call predecessors, (26), 23 states have call successors, (26) [2021-12-14 19:29:54,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 179 states to 179 states and 205 transitions. [2021-12-14 19:29:54,457 INFO L78 Accepts]: Start accepts. Automaton has 179 states and 205 transitions. Word has length 11 [2021-12-14 19:29:54,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:54,457 INFO L470 AbstractCegarLoop]: Abstraction has 179 states and 205 transitions. [2021-12-14 19:29:54,457 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:54,457 INFO L276 IsEmpty]: Start isEmpty. Operand 179 states and 205 transitions. [2021-12-14 19:29:54,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-14 19:29:54,458 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:54,458 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:29:54,466 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Forceful destruction successful, exit code 0 [2021-12-14 19:29:54,658 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:54,658 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting nondet_treeErr3REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:54,659 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:54,659 INFO L85 PathProgramCache]: Analyzing trace with hash 873486781, now seen corresponding path program 1 times [2021-12-14 19:29:54,659 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:54,659 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1262878586] [2021-12-14 19:29:54,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:54,659 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:54,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:54,660 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:54,662 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Waiting until timeout for monitored process [2021-12-14 19:29:54,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:54,708 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-14 19:29:54,709 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:54,718 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 6 treesize of output 5 [2021-12-14 19:29:54,756 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:54,756 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:54,757 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:54,757 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1262878586] [2021-12-14 19:29:54,757 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1262878586] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:54,757 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:54,757 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-14 19:29:54,757 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [167778917] [2021-12-14 19:29:54,757 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:54,758 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-14 19:29:54,758 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:54,758 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-14 19:29:54,758 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 19:29:54,759 INFO L87 Difference]: Start difference. First operand 179 states and 205 transitions. Second operand has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:55,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:55,115 INFO L93 Difference]: Finished difference Result 185 states and 215 transitions. [2021-12-14 19:29:55,115 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-14 19:29:55,115 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-14 19:29:55,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:55,116 INFO L225 Difference]: With dead ends: 185 [2021-12-14 19:29:55,116 INFO L226 Difference]: Without dead ends: 185 [2021-12-14 19:29:55,117 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-14 19:29:55,117 INFO L933 BasicCegarLoop]: 153 mSDtfsCounter, 93 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 224 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 248 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 224 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:55,117 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [100 Valid, 242 Invalid, 248 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 224 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-14 19:29:55,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2021-12-14 19:29:55,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 182. [2021-12-14 19:29:55,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 182 states, 96 states have (on average 1.6354166666666667) internal successors, (157), 147 states have internal predecessors, (157), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (28), 26 states have call predecessors, (28), 24 states have call successors, (28) [2021-12-14 19:29:55,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 182 states to 182 states and 209 transitions. [2021-12-14 19:29:55,124 INFO L78 Accepts]: Start accepts. Automaton has 182 states and 209 transitions. Word has length 11 [2021-12-14 19:29:55,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:55,124 INFO L470 AbstractCegarLoop]: Abstraction has 182 states and 209 transitions. [2021-12-14 19:29:55,124 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 19:29:55,124 INFO L276 IsEmpty]: Start isEmpty. Operand 182 states and 209 transitions. [2021-12-14 19:29:55,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-14 19:29:55,124 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:55,124 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:29:55,133 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Forceful destruction successful, exit code 0 [2021-12-14 19:29:55,331 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:55,331 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting sizeErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:55,332 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:55,332 INFO L85 PathProgramCache]: Analyzing trace with hash -1280810199, now seen corresponding path program 1 times [2021-12-14 19:29:55,332 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:55,332 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1155304443] [2021-12-14 19:29:55,332 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:55,332 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:55,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:55,333 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:55,335 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2021-12-14 19:29:55,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:55,373 INFO L263 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-14 19:29:55,374 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:55,464 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:29:55,464 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:29:55,464 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:55,464 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1155304443] [2021-12-14 19:29:55,464 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1155304443] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:29:55,464 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:29:55,464 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-14 19:29:55,464 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1342263903] [2021-12-14 19:29:55,464 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:29:55,465 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 19:29:55,465 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:55,465 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 19:29:55,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-14 19:29:55,465 INFO L87 Difference]: Start difference. First operand 182 states and 209 transitions. Second operand has 7 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-14 19:29:55,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:29:55,560 INFO L93 Difference]: Finished difference Result 242 states and 282 transitions. [2021-12-14 19:29:55,561 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-14 19:29:55,561 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2021-12-14 19:29:55,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:29:55,562 INFO L225 Difference]: With dead ends: 242 [2021-12-14 19:29:55,562 INFO L226 Difference]: Without dead ends: 242 [2021-12-14 19:29:55,562 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-12-14 19:29:55,563 INFO L933 BasicCegarLoop]: 198 mSDtfsCounter, 90 mSDsluCounter, 956 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 1154 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 19:29:55,563 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [90 Valid, 1154 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 19:29:55,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2021-12-14 19:29:55,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 204. [2021-12-14 19:29:55,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 110 states have (on average 1.5909090909090908) internal successors, (175), 161 states have internal predecessors, (175), 31 states have call successors, (31), 9 states have call predecessors, (31), 10 states have return successors, (35), 33 states have call predecessors, (35), 31 states have call successors, (35) [2021-12-14 19:29:55,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 241 transitions. [2021-12-14 19:29:55,572 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 241 transitions. Word has length 17 [2021-12-14 19:29:55,572 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:29:55,572 INFO L470 AbstractCegarLoop]: Abstraction has 204 states and 241 transitions. [2021-12-14 19:29:55,572 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-14 19:29:55,572 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 241 transitions. [2021-12-14 19:29:55,573 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2021-12-14 19:29:55,573 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:29:55,573 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:29:55,583 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Forceful destruction successful, exit code 0 [2021-12-14 19:29:55,780 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:29:55,780 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting nondet_treeErr2REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:29:55,781 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:29:55,781 INFO L85 PathProgramCache]: Analyzing trace with hash -1539264760, now seen corresponding path program 1 times [2021-12-14 19:29:55,781 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:29:55,781 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [664335305] [2021-12-14 19:29:55,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:55,782 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:29:55,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:29:55,783 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:29:55,785 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Waiting until timeout for monitored process [2021-12-14 19:29:55,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:55,922 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-14 19:29:55,923 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:55,940 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 6 treesize of output 5 [2021-12-14 19:29:56,156 INFO L354 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-14 19:29:56,156 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 33 [2021-12-14 19:29:56,173 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-12-14 19:29:56,173 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:29:56,346 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:29:56,346 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [664335305] [2021-12-14 19:29:56,346 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [664335305] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:29:56,346 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [80400581] [2021-12-14 19:29:56,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:29:56,346 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-14 19:29:56,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-14 19:29:56,348 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-14 19:29:56,365 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2021-12-14 19:29:56,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:29:56,503 INFO L263 TraceCheckSpWp]: Trace formula consists of 211 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-14 19:29:56,505 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:29:56,524 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 6 treesize of output 5 [2021-12-14 19:29:58,693 INFO L354 Elim1Store]: treesize reduction 12, result has 40.0 percent of original size [2021-12-14 19:29:58,694 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 21 [2021-12-14 19:29:58,702 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-12-14 19:29:58,702 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:29:58,793 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [80400581] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:29:58,793 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:29:58,793 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2021-12-14 19:29:58,794 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [941568172] [2021-12-14 19:29:58,794 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:29:58,794 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-14 19:29:58,794 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:29:58,794 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-14 19:29:58,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=27, Unknown=1, NotChecked=0, Total=42 [2021-12-14 19:29:58,795 INFO L87 Difference]: Start difference. First operand 204 states and 241 transitions. Second operand has 6 states, 5 states have (on average 5.4) internal successors, (27), 6 states have internal predecessors, (27), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2021-12-14 19:30:05,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:05,147 INFO L93 Difference]: Finished difference Result 210 states and 249 transitions. [2021-12-14 19:30:05,147 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-14 19:30:05,148 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 6 states have internal predecessors, (27), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 29 [2021-12-14 19:30:05,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:05,149 INFO L225 Difference]: With dead ends: 210 [2021-12-14 19:30:05,149 INFO L226 Difference]: Without dead ends: 210 [2021-12-14 19:30:05,149 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 54 SyntacticMatches, 11 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=26, Invalid=44, Unknown=2, NotChecked=0, Total=72 [2021-12-14 19:30:05,150 INFO L933 BasicCegarLoop]: 152 mSDtfsCounter, 86 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 203 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 358 SdHoareTripleChecker+Invalid, 517 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 203 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 291 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:05,150 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [92 Valid, 358 Invalid, 517 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 203 Invalid, 0 Unknown, 291 Unchecked, 0.3s Time] [2021-12-14 19:30:05,151 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 210 states. [2021-12-14 19:30:05,154 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 210 to 208. [2021-12-14 19:30:05,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 208 states, 113 states have (on average 1.584070796460177) internal successors, (179), 164 states have internal predecessors, (179), 31 states have call successors, (31), 9 states have call predecessors, (31), 11 states have return successors, (39), 34 states have call predecessors, (39), 31 states have call successors, (39) [2021-12-14 19:30:05,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 208 states to 208 states and 249 transitions. [2021-12-14 19:30:05,156 INFO L78 Accepts]: Start accepts. Automaton has 208 states and 249 transitions. Word has length 29 [2021-12-14 19:30:05,156 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:05,156 INFO L470 AbstractCegarLoop]: Abstraction has 208 states and 249 transitions. [2021-12-14 19:30:05,165 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 6 states have internal predecessors, (27), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2021-12-14 19:30:05,165 INFO L276 IsEmpty]: Start isEmpty. Operand 208 states and 249 transitions. [2021-12-14 19:30:05,168 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-14 19:30:05,168 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:05,168 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:05,177 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:05,378 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:05,569 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:05,570 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting nondet_treeErr3REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:05,570 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:05,570 INFO L85 PathProgramCache]: Analyzing trace with hash 1070284721, now seen corresponding path program 1 times [2021-12-14 19:30:05,570 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:05,570 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [226214676] [2021-12-14 19:30:05,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:05,571 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:05,571 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:05,571 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:05,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Waiting until timeout for monitored process [2021-12-14 19:30:05,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:05,683 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-14 19:30:05,685 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:05,696 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 6 treesize of output 5 [2021-12-14 19:30:05,703 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 6 treesize of output 5 [2021-12-14 19:30:09,935 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 19:30:09,936 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 12 treesize of output 14 [2021-12-14 19:30:09,943 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-14 19:30:09,943 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 20 treesize of output 20 [2021-12-14 19:30:09,958 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:09,958 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:10,171 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:10,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [226214676] [2021-12-14 19:30:10,171 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [226214676] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:10,171 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1310241955] [2021-12-14 19:30:10,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:10,171 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-14 19:30:10,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-14 19:30:10,172 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-14 19:30:10,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Waiting until timeout for monitored process [2021-12-14 19:30:10,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:10,323 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-14 19:30:10,324 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:10,341 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 6 treesize of output 5 [2021-12-14 19:30:10,347 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 6 treesize of output 5 [2021-12-14 19:30:14,554 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 19:30:14,555 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 12 treesize of output 14 [2021-12-14 19:30:14,563 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-14 19:30:14,563 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 17 treesize of output 17 [2021-12-14 19:30:14,569 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:14,569 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:14,762 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1310241955] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:14,762 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:14,762 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2021-12-14 19:30:14,762 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [109876133] [2021-12-14 19:30:14,762 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:14,762 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 19:30:14,762 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:14,763 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 19:30:14,763 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2021-12-14 19:30:14,763 INFO L87 Difference]: Start difference. First operand 208 states and 249 transitions. Second operand has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-14 19:30:15,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:15,300 INFO L93 Difference]: Finished difference Result 227 states and 281 transitions. [2021-12-14 19:30:15,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 19:30:15,301 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2021-12-14 19:30:15,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:15,302 INFO L225 Difference]: With dead ends: 227 [2021-12-14 19:30:15,302 INFO L226 Difference]: Without dead ends: 227 [2021-12-14 19:30:15,303 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 40 SyntacticMatches, 6 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2021-12-14 19:30:15,303 INFO L933 BasicCegarLoop]: 144 mSDtfsCounter, 102 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 310 SdHoareTripleChecker+Invalid, 512 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 183 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:15,303 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [108 Valid, 310 Invalid, 512 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 296 Invalid, 0 Unknown, 183 Unchecked, 0.5s Time] [2021-12-14 19:30:15,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 227 states. [2021-12-14 19:30:15,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 227 to 224. [2021-12-14 19:30:15,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 224 states, 124 states have (on average 1.532258064516129) internal successors, (190), 176 states have internal predecessors, (190), 34 states have call successors, (34), 10 states have call predecessors, (34), 13 states have return successors, (48), 37 states have call predecessors, (48), 34 states have call successors, (48) [2021-12-14 19:30:15,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 272 transitions. [2021-12-14 19:30:15,310 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 272 transitions. Word has length 25 [2021-12-14 19:30:15,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:15,310 INFO L470 AbstractCegarLoop]: Abstraction has 224 states and 272 transitions. [2021-12-14 19:30:15,310 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-14 19:30:15,310 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 272 transitions. [2021-12-14 19:30:15,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-14 19:30:15,311 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:15,312 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:15,317 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:15,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:15,715 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:15,715 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting minErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:15,715 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:15,715 INFO L85 PathProgramCache]: Analyzing trace with hash -1668050227, now seen corresponding path program 1 times [2021-12-14 19:30:15,715 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:15,716 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1557658787] [2021-12-14 19:30:15,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:15,716 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:15,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:15,716 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:15,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Waiting until timeout for monitored process [2021-12-14 19:30:15,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:15,793 INFO L263 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-14 19:30:15,798 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:15,809 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 6 treesize of output 5 [2021-12-14 19:30:15,922 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:15,922 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:16,119 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:16,119 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:16,119 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1557658787] [2021-12-14 19:30:16,119 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1557658787] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 19:30:16,119 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:16,119 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2021-12-14 19:30:16,120 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [252784615] [2021-12-14 19:30:16,120 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:16,120 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 19:30:16,120 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:16,120 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 19:30:16,120 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2021-12-14 19:30:16,121 INFO L87 Difference]: Start difference. First operand 224 states and 272 transitions. Second operand has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-12-14 19:30:17,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:17,150 INFO L93 Difference]: Finished difference Result 244 states and 296 transitions. [2021-12-14 19:30:17,150 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-12-14 19:30:17,150 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 25 [2021-12-14 19:30:17,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:17,152 INFO L225 Difference]: With dead ends: 244 [2021-12-14 19:30:17,152 INFO L226 Difference]: Without dead ends: 244 [2021-12-14 19:30:17,152 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 30 SyntacticMatches, 10 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2021-12-14 19:30:17,152 INFO L933 BasicCegarLoop]: 162 mSDtfsCounter, 158 mSDsluCounter, 507 mSDsCounter, 0 mSdLazyCounter, 982 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 162 SdHoareTripleChecker+Valid, 669 SdHoareTripleChecker+Invalid, 1090 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 982 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 55 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:17,152 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [162 Valid, 669 Invalid, 1090 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 982 Invalid, 0 Unknown, 55 Unchecked, 0.9s Time] [2021-12-14 19:30:17,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2021-12-14 19:30:17,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 236. [2021-12-14 19:30:17,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 236 states, 135 states have (on average 1.5185185185185186) internal successors, (205), 185 states have internal predecessors, (205), 36 states have call successors, (36), 11 states have call predecessors, (36), 14 states have return successors, (50), 39 states have call predecessors, (50), 36 states have call successors, (50) [2021-12-14 19:30:17,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 236 states to 236 states and 291 transitions. [2021-12-14 19:30:17,160 INFO L78 Accepts]: Start accepts. Automaton has 236 states and 291 transitions. Word has length 25 [2021-12-14 19:30:17,160 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:17,160 INFO L470 AbstractCegarLoop]: Abstraction has 236 states and 291 transitions. [2021-12-14 19:30:17,160 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.25) internal successors, (18), 8 states have internal predecessors, (18), 3 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-12-14 19:30:17,160 INFO L276 IsEmpty]: Start isEmpty. Operand 236 states and 291 transitions. [2021-12-14 19:30:17,161 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-14 19:30:17,161 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:17,161 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:17,170 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Ended with exit code 0 [2021-12-14 19:30:17,361 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:17,361 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting minErr1REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:17,362 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:17,362 INFO L85 PathProgramCache]: Analyzing trace with hash -1668050226, now seen corresponding path program 1 times [2021-12-14 19:30:17,362 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:17,362 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [165245981] [2021-12-14 19:30:17,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:17,363 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:17,363 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:17,363 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:17,364 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Waiting until timeout for monitored process [2021-12-14 19:30:17,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:17,440 INFO L263 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 20 conjunts are in the unsatisfiable core [2021-12-14 19:30:17,441 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:17,448 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 6 treesize of output 5 [2021-12-14 19:30:17,611 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:17,611 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:18,856 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 19:30:18,856 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:18,856 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [165245981] [2021-12-14 19:30:18,856 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [165245981] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 19:30:18,856 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:18,856 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2021-12-14 19:30:18,857 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [792250737] [2021-12-14 19:30:18,857 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:18,857 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-14 19:30:18,857 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:18,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-14 19:30:18,858 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=204, Unknown=0, NotChecked=0, Total=240 [2021-12-14 19:30:18,858 INFO L87 Difference]: Start difference. First operand 236 states and 291 transitions. Second operand has 16 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2021-12-14 19:30:22,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:22,012 INFO L93 Difference]: Finished difference Result 261 states and 327 transitions. [2021-12-14 19:30:22,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-14 19:30:22,012 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 25 [2021-12-14 19:30:22,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:22,014 INFO L225 Difference]: With dead ends: 261 [2021-12-14 19:30:22,014 INFO L226 Difference]: Without dead ends: 261 [2021-12-14 19:30:22,014 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2021-12-14 19:30:22,014 INFO L933 BasicCegarLoop]: 156 mSDtfsCounter, 143 mSDsluCounter, 573 mSDsCounter, 0 mSdLazyCounter, 1482 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 148 SdHoareTripleChecker+Valid, 729 SdHoareTripleChecker+Invalid, 1573 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 1482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 47 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:22,015 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [148 Valid, 729 Invalid, 1573 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 1482 Invalid, 0 Unknown, 47 Unchecked, 2.9s Time] [2021-12-14 19:30:22,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 261 states. [2021-12-14 19:30:22,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 261 to 252. [2021-12-14 19:30:22,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 252 states, 147 states have (on average 1.4965986394557824) internal successors, (220), 197 states have internal predecessors, (220), 39 states have call successors, (39), 12 states have call predecessors, (39), 15 states have return successors, (53), 42 states have call predecessors, (53), 39 states have call successors, (53) [2021-12-14 19:30:22,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 252 states to 252 states and 312 transitions. [2021-12-14 19:30:22,021 INFO L78 Accepts]: Start accepts. Automaton has 252 states and 312 transitions. Word has length 25 [2021-12-14 19:30:22,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:22,021 INFO L470 AbstractCegarLoop]: Abstraction has 252 states and 312 transitions. [2021-12-14 19:30:22,021 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 12 states have internal predecessors, (30), 5 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2021-12-14 19:30:22,021 INFO L276 IsEmpty]: Start isEmpty. Operand 252 states and 312 transitions. [2021-12-14 19:30:22,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2021-12-14 19:30:22,022 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:22,022 INFO L514 BasicCegarLoop]: trace histogram [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 19:30:22,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:22,222 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:22,222 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting tree_inorderErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:22,223 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:22,223 INFO L85 PathProgramCache]: Analyzing trace with hash 369889479, now seen corresponding path program 1 times [2021-12-14 19:30:22,223 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:22,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [191504616] [2021-12-14 19:30:22,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:22,223 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:22,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:22,224 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:22,225 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Waiting until timeout for monitored process [2021-12-14 19:30:22,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:22,278 INFO L263 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-14 19:30:22,279 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:22,327 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 19:30:22,327 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:30:22,328 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:22,328 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [191504616] [2021-12-14 19:30:22,328 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [191504616] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:30:22,328 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:30:22,328 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-14 19:30:22,328 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [339789291] [2021-12-14 19:30:22,328 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:30:22,329 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-14 19:30:22,329 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:22,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-14 19:30:22,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-14 19:30:22,330 INFO L87 Difference]: Start difference. First operand 252 states and 312 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-14 19:30:22,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:22,342 INFO L93 Difference]: Finished difference Result 242 states and 293 transitions. [2021-12-14 19:30:22,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-14 19:30:22,342 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2021-12-14 19:30:22,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:22,343 INFO L225 Difference]: With dead ends: 242 [2021-12-14 19:30:22,343 INFO L226 Difference]: Without dead ends: 226 [2021-12-14 19:30:22,343 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-14 19:30:22,344 INFO L933 BasicCegarLoop]: 188 mSDtfsCounter, 0 mSDsluCounter, 560 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 748 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:22,344 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 748 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-14 19:30:22,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2021-12-14 19:30:22,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 226. [2021-12-14 19:30:22,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 226 states, 130 states have (on average 1.5307692307692307) internal successors, (199), 181 states have internal predecessors, (199), 31 states have call successors, (31), 10 states have call predecessors, (31), 14 states have return successors, (47), 34 states have call predecessors, (47), 31 states have call successors, (47) [2021-12-14 19:30:22,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 277 transitions. [2021-12-14 19:30:22,353 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 277 transitions. Word has length 30 [2021-12-14 19:30:22,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:22,353 INFO L470 AbstractCegarLoop]: Abstraction has 226 states and 277 transitions. [2021-12-14 19:30:22,353 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 4 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-14 19:30:22,353 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 277 transitions. [2021-12-14 19:30:22,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2021-12-14 19:30:22,354 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:22,354 INFO L514 BasicCegarLoop]: trace histogram [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] [2021-12-14 19:30:22,364 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:22,562 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:22,562 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting sizeErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:22,562 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:22,563 INFO L85 PathProgramCache]: Analyzing trace with hash -648076771, now seen corresponding path program 1 times [2021-12-14 19:30:22,563 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:22,563 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [959119928] [2021-12-14 19:30:22,563 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:22,563 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:22,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:22,564 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:22,565 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Waiting until timeout for monitored process [2021-12-14 19:30:22,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:22,634 INFO L263 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-14 19:30:22,634 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:22,709 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2021-12-14 19:30:22,709 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-14 19:30:22,709 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:22,709 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [959119928] [2021-12-14 19:30:22,709 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [959119928] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 19:30:22,709 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 19:30:22,709 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2021-12-14 19:30:22,709 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1928013284] [2021-12-14 19:30:22,709 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 19:30:22,709 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-14 19:30:22,709 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:22,710 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-14 19:30:22,710 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2021-12-14 19:30:22,710 INFO L87 Difference]: Start difference. First operand 226 states and 277 transitions. Second operand has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2021-12-14 19:30:22,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:22,889 INFO L93 Difference]: Finished difference Result 232 states and 286 transitions. [2021-12-14 19:30:22,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-14 19:30:22,889 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 31 [2021-12-14 19:30:22,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:22,890 INFO L225 Difference]: With dead ends: 232 [2021-12-14 19:30:22,890 INFO L226 Difference]: Without dead ends: 228 [2021-12-14 19:30:22,891 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2021-12-14 19:30:22,891 INFO L933 BasicCegarLoop]: 171 mSDtfsCounter, 109 mSDsluCounter, 883 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 113 SdHoareTripleChecker+Valid, 1054 SdHoareTripleChecker+Invalid, 164 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:22,891 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [113 Valid, 1054 Invalid, 164 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-14 19:30:22,892 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2021-12-14 19:30:22,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 226. [2021-12-14 19:30:22,895 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 226 states, 130 states have (on average 1.5153846153846153) internal successors, (197), 181 states have internal predecessors, (197), 31 states have call successors, (31), 10 states have call predecessors, (31), 14 states have return successors, (47), 34 states have call predecessors, (47), 31 states have call successors, (47) [2021-12-14 19:30:22,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 275 transitions. [2021-12-14 19:30:22,897 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 275 transitions. Word has length 31 [2021-12-14 19:30:22,897 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:22,897 INFO L470 AbstractCegarLoop]: Abstraction has 226 states and 275 transitions. [2021-12-14 19:30:22,897 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2021-12-14 19:30:22,897 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 275 transitions. [2021-12-14 19:30:22,897 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2021-12-14 19:30:22,898 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:22,898 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:22,905 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:23,104 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:23,105 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting minErr0REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:23,105 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:23,105 INFO L85 PathProgramCache]: Analyzing trace with hash -2088825952, now seen corresponding path program 1 times [2021-12-14 19:30:23,106 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:23,106 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1392330658] [2021-12-14 19:30:23,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:23,106 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:23,106 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:23,107 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:23,108 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (16)] Waiting until timeout for monitored process [2021-12-14 19:30:23,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:23,205 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 37 conjunts are in the unsatisfiable core [2021-12-14 19:30:23,207 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:23,254 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 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-14 19:30:23,259 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 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-14 19:30:23,319 INFO L354 Elim1Store]: treesize reduction 27, result has 25.0 percent of original size [2021-12-14 19:30:23,319 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 22 [2021-12-14 19:30:23,328 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 19:30:23,329 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 23 treesize of output 22 [2021-12-14 19:30:23,478 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 19 treesize of output 7 [2021-12-14 19:30:23,480 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 19 treesize of output 7 [2021-12-14 19:30:23,556 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-14 19:30:23,557 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:24,124 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-14 19:30:24,125 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:24,125 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1392330658] [2021-12-14 19:30:24,125 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1392330658] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 19:30:24,125 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:24,125 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 15 [2021-12-14 19:30:24,125 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1776767438] [2021-12-14 19:30:24,125 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:24,125 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-12-14 19:30:24,125 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:24,126 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-12-14 19:30:24,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=182, Unknown=0, NotChecked=0, Total=210 [2021-12-14 19:30:24,126 INFO L87 Difference]: Start difference. First operand 226 states and 275 transitions. Second operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-14 19:30:24,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:24,865 INFO L93 Difference]: Finished difference Result 244 states and 299 transitions. [2021-12-14 19:30:24,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-12-14 19:30:24,866 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2021-12-14 19:30:24,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:24,866 INFO L225 Difference]: With dead ends: 244 [2021-12-14 19:30:24,867 INFO L226 Difference]: Without dead ends: 244 [2021-12-14 19:30:24,867 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=59, Invalid=403, Unknown=0, NotChecked=0, Total=462 [2021-12-14 19:30:24,867 INFO L933 BasicCegarLoop]: 191 mSDtfsCounter, 44 mSDsluCounter, 2033 mSDsCounter, 0 mSdLazyCounter, 345 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 2224 SdHoareTripleChecker+Invalid, 466 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 345 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 107 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:24,868 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 2224 Invalid, 466 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 345 Invalid, 0 Unknown, 107 Unchecked, 0.5s Time] [2021-12-14 19:30:24,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2021-12-14 19:30:24,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 233. [2021-12-14 19:30:24,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 135 states have (on average 1.5037037037037038) internal successors, (203), 186 states have internal predecessors, (203), 31 states have call successors, (31), 12 states have call predecessors, (31), 16 states have return successors, (47), 34 states have call predecessors, (47), 31 states have call successors, (47) [2021-12-14 19:30:24,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 281 transitions. [2021-12-14 19:30:24,873 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 281 transitions. Word has length 31 [2021-12-14 19:30:24,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:24,873 INFO L470 AbstractCegarLoop]: Abstraction has 233 states and 281 transitions. [2021-12-14 19:30:24,873 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-14 19:30:24,873 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 281 transitions. [2021-12-14 19:30:24,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-14 19:30:24,874 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:24,874 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:24,882 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (16)] Ended with exit code 0 [2021-12-14 19:30:25,081 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:25,081 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting nondet_treeErr5REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:25,081 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:25,081 INFO L85 PathProgramCache]: Analyzing trace with hash -931523584, now seen corresponding path program 1 times [2021-12-14 19:30:25,082 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:25,082 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [215707284] [2021-12-14 19:30:25,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:25,082 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:25,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:25,083 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:25,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (17)] Waiting until timeout for monitored process [2021-12-14 19:30:25,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:25,322 INFO L263 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 20 conjunts are in the unsatisfiable core [2021-12-14 19:30:25,324 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:25,350 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 6 treesize of output 5 [2021-12-14 19:30:25,355 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 6 treesize of output 5 [2021-12-14 19:30:29,628 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 19:30:29,628 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 12 treesize of output 14 [2021-12-14 19:30:29,637 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-14 19:30:29,637 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 20 treesize of output 20 [2021-12-14 19:30:29,656 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 42 proven. 21 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2021-12-14 19:30:29,657 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:29,885 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:29,885 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [215707284] [2021-12-14 19:30:29,885 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [215707284] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:29,885 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [867183467] [2021-12-14 19:30:29,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:29,885 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-14 19:30:29,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-14 19:30:29,886 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-14 19:30:29,887 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Waiting until timeout for monitored process [2021-12-14 19:30:30,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:30,125 INFO L263 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 20 conjunts are in the unsatisfiable core [2021-12-14 19:30:30,127 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:30,150 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 6 treesize of output 5 [2021-12-14 19:30:30,156 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 6 treesize of output 5 [2021-12-14 19:30:34,369 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-14 19:30:34,370 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 12 treesize of output 14 [2021-12-14 19:30:34,377 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-14 19:30:34,377 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 19 treesize of output 19 [2021-12-14 19:30:34,383 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 42 proven. 21 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2021-12-14 19:30:34,383 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:34,563 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [867183467] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:34,563 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:34,563 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2021-12-14 19:30:34,563 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1810418646] [2021-12-14 19:30:34,563 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:34,564 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 19:30:34,564 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:34,564 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 19:30:34,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2021-12-14 19:30:34,564 INFO L87 Difference]: Start difference. First operand 233 states and 281 transitions. Second operand has 7 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-14 19:30:35,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:35,118 INFO L93 Difference]: Finished difference Result 238 states and 292 transitions. [2021-12-14 19:30:35,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 19:30:35,119 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 45 [2021-12-14 19:30:35,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:35,120 INFO L225 Difference]: With dead ends: 238 [2021-12-14 19:30:35,120 INFO L226 Difference]: Without dead ends: 238 [2021-12-14 19:30:35,120 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 78 SyntacticMatches, 8 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2021-12-14 19:30:35,121 INFO L933 BasicCegarLoop]: 138 mSDtfsCounter, 170 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 371 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 176 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 597 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 371 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 174 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:35,121 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [176 Valid, 312 Invalid, 597 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 371 Invalid, 0 Unknown, 174 Unchecked, 0.5s Time] [2021-12-14 19:30:35,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2021-12-14 19:30:35,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 234. [2021-12-14 19:30:35,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 234 states, 136 states have (on average 1.5073529411764706) internal successors, (205), 186 states have internal predecessors, (205), 31 states have call successors, (31), 12 states have call predecessors, (31), 16 states have return successors, (47), 35 states have call predecessors, (47), 31 states have call successors, (47) [2021-12-14 19:30:35,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 234 states to 234 states and 283 transitions. [2021-12-14 19:30:35,126 INFO L78 Accepts]: Start accepts. Automaton has 234 states and 283 transitions. Word has length 45 [2021-12-14 19:30:35,126 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:35,126 INFO L470 AbstractCegarLoop]: Abstraction has 234 states and 283 transitions. [2021-12-14 19:30:35,126 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.5) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-14 19:30:35,126 INFO L276 IsEmpty]: Start isEmpty. Operand 234 states and 283 transitions. [2021-12-14 19:30:35,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-14 19:30:35,127 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:35,127 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2021-12-14 19:30:35,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (17)] Ended with exit code 0 [2021-12-14 19:30:35,339 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:35,536 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2021-12-14 19:30:35,536 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting nondet_treeErr4REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:35,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:35,536 INFO L85 PathProgramCache]: Analyzing trace with hash -931523585, now seen corresponding path program 1 times [2021-12-14 19:30:35,537 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:35,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2041471915] [2021-12-14 19:30:35,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:35,537 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:35,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:35,538 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:35,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (19)] Waiting until timeout for monitored process [2021-12-14 19:30:35,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:35,752 INFO L263 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-14 19:30:35,754 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:35,774 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 6 treesize of output 5 [2021-12-14 19:30:35,926 INFO L354 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-14 19:30:35,926 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 24 treesize of output 31 [2021-12-14 19:30:35,934 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 42 proven. 13 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2021-12-14 19:30:35,934 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:36,024 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:36,024 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2041471915] [2021-12-14 19:30:36,025 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [2041471915] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:36,025 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1581501944] [2021-12-14 19:30:36,025 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 19:30:36,025 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-14 19:30:36,025 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-14 19:30:36,026 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-14 19:30:36,039 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (20)] Waiting until timeout for monitored process [2021-12-14 19:30:36,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 19:30:36,240 INFO L263 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-14 19:30:36,241 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:36,269 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 6 treesize of output 5 [2021-12-14 19:30:38,380 INFO L354 Elim1Store]: treesize reduction 12, result has 40.0 percent of original size [2021-12-14 19:30:38,381 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 21 [2021-12-14 19:30:38,388 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 42 proven. 13 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2021-12-14 19:30:38,388 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:38,466 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1581501944] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:38,466 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:38,466 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2021-12-14 19:30:38,467 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918000731] [2021-12-14 19:30:38,467 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:38,467 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-14 19:30:38,467 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:38,467 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-14 19:30:38,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=27, Unknown=1, NotChecked=0, Total=42 [2021-12-14 19:30:38,468 INFO L87 Difference]: Start difference. First operand 234 states and 283 transitions. Second operand has 6 states, 5 states have (on average 6.6) internal successors, (33), 6 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 19:30:44,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 19:30:44,745 INFO L93 Difference]: Finished difference Result 237 states and 291 transitions. [2021-12-14 19:30:44,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-14 19:30:44,746 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 6.6) internal successors, (33), 6 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 45 [2021-12-14 19:30:44,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 19:30:44,747 INFO L225 Difference]: With dead ends: 237 [2021-12-14 19:30:44,747 INFO L226 Difference]: Without dead ends: 237 [2021-12-14 19:30:44,747 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 88 SyntacticMatches, 10 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=26, Invalid=44, Unknown=2, NotChecked=0, Total=72 [2021-12-14 19:30:44,747 INFO L933 BasicCegarLoop]: 156 mSDtfsCounter, 83 mSDsluCounter, 210 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 511 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 294 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-14 19:30:44,748 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [89 Valid, 366 Invalid, 511 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 196 Invalid, 0 Unknown, 294 Unchecked, 0.2s Time] [2021-12-14 19:30:44,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2021-12-14 19:30:44,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 233. [2021-12-14 19:30:44,753 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 135 states have (on average 1.5037037037037038) internal successors, (203), 186 states have internal predecessors, (203), 31 states have call successors, (31), 12 states have call predecessors, (31), 16 states have return successors, (47), 34 states have call predecessors, (47), 31 states have call successors, (47) [2021-12-14 19:30:44,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 281 transitions. [2021-12-14 19:30:44,754 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 281 transitions. Word has length 45 [2021-12-14 19:30:44,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 19:30:44,755 INFO L470 AbstractCegarLoop]: Abstraction has 233 states and 281 transitions. [2021-12-14 19:30:44,755 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 6.6) internal successors, (33), 6 states have internal predecessors, (33), 4 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-14 19:30:44,755 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 281 transitions. [2021-12-14 19:30:44,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2021-12-14 19:30:44,757 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 19:30:44,757 INFO L514 BasicCegarLoop]: trace histogram [6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1] [2021-12-14 19:30:44,760 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (20)] Forceful destruction successful, exit code 0 [2021-12-14 19:30:44,968 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (19)] Ended with exit code 0 [2021-12-14 19:30:45,160 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-14 19:30:45,160 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting nondet_treeErr2REQUIRES_VIOLATION === [nondet_treeErr0REQUIRES_VIOLATION, nondet_treeErr1REQUIRES_VIOLATION, nondet_treeErr2REQUIRES_VIOLATION, nondet_treeErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-14 19:30:45,161 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 19:30:45,161 INFO L85 PathProgramCache]: Analyzing trace with hash 1901629290, now seen corresponding path program 2 times [2021-12-14 19:30:45,161 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-14 19:30:45,161 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1909318562] [2021-12-14 19:30:45,161 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 19:30:45,162 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-14 19:30:45,162 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-14 19:30:45,162 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-14 19:30:45,163 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (21)] Waiting until timeout for monitored process [2021-12-14 19:30:45,323 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 19:30:45,324 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 19:30:45,332 INFO L263 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 19:30:45,333 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:45,348 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 6 treesize of output 5 [2021-12-14 19:30:49,667 INFO L354 Elim1Store]: treesize reduction 38, result has 39.7 percent of original size [2021-12-14 19:30:49,667 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 28 treesize of output 44 [2021-12-14 19:30:49,735 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 41 proven. 27 refuted. 3 times theorem prover too weak. 19 trivial. 0 not checked. [2021-12-14 19:30:49,735 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:51,829 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-14 19:30:51,829 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1909318562] [2021-12-14 19:30:51,829 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1909318562] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:51,829 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [2033736086] [2021-12-14 19:30:51,829 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 19:30:51,829 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-14 19:30:51,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-14 19:30:51,831 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-14 19:30:51,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (22)] Waiting until timeout for monitored process [2021-12-14 19:30:52,020 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-14 19:30:52,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1288614519] [2021-12-14 19:30:52,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 19:30:52,020 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 19:30:52,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 19:30:52,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (22)] Forceful destruction successful, exit code 1 [2021-12-14 19:30:52,024 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 19:30:52,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2021-12-14 19:30:52,170 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 19:30:52,170 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 19:30:52,173 INFO L263 TraceCheckSpWp]: Trace formula consists of 334 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 19:30:52,174 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 19:30:52,189 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 6 treesize of output 5 [2021-12-14 19:30:56,639 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-14 19:30:56,659 INFO L354 Elim1Store]: treesize reduction 24, result has 46.7 percent of original size [2021-12-14 19:30:56,660 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 21 treesize of output 35 [2021-12-14 19:30:56,677 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 41 proven. 30 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2021-12-14 19:30:56,678 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 19:30:56,819 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1288614519] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 19:30:56,819 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-14 19:30:56,819 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 9 [2021-12-14 19:30:56,819 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [528471230] [2021-12-14 19:30:56,819 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-14 19:30:56,819 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-14 19:30:56,820 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-14 19:30:56,820 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-14 19:30:56,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=97, Unknown=4, NotChecked=0, Total=132 [2021-12-14 19:30:56,820 INFO L87 Difference]: Start difference. First operand 233 states and 281 transitions. Second operand has 10 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 7 states have call successors, (10), 2 states have call predecessors, (10), 5 states have return successors, (9), 6 states have call predecessors, (9), 7 states have call successors, (9)