/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/verifythis/tree_del_iter_incorrect.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-d966a43 [2022-01-31 23:30:06,221 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-01-31 23:30:06,222 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-01-31 23:30:06,268 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-01-31 23:30:06,268 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-01-31 23:30:06,269 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-01-31 23:30:06,270 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-01-31 23:30:06,273 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-01-31 23:30:06,275 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-01-31 23:30:06,276 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-01-31 23:30:06,276 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-01-31 23:30:06,277 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-01-31 23:30:06,277 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-01-31 23:30:06,278 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-01-31 23:30:06,278 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-01-31 23:30:06,279 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-01-31 23:30:06,279 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-01-31 23:30:06,280 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-01-31 23:30:06,281 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-01-31 23:30:06,282 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-01-31 23:30:06,283 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-01-31 23:30:06,288 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-01-31 23:30:06,289 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-01-31 23:30:06,290 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-01-31 23:30:06,291 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-01-31 23:30:06,291 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-01-31 23:30:06,291 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-01-31 23:30:06,292 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-01-31 23:30:06,292 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-01-31 23:30:06,293 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-01-31 23:30:06,293 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-01-31 23:30:06,293 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-01-31 23:30:06,294 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-01-31 23:30:06,294 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-01-31 23:30:06,295 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-01-31 23:30:06,295 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-01-31 23:30:06,295 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-01-31 23:30:06,296 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-01-31 23:30:06,296 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-01-31 23:30:06,296 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-01-31 23:30:06,297 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-01-31 23:30:06,297 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-01-31 23:30:06,303 INFO L113 SettingsManager]: Loading preferences was successful [2022-01-31 23:30:06,303 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-01-31 23:30:06,304 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-01-31 23:30:06,304 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-01-31 23:30:06,304 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-01-31 23:30:06,304 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-01-31 23:30:06,304 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * Use constant arrays=true [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-01-31 23:30:06,305 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-01-31 23:30:06,305 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-31 23:30:06,306 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=AcceleratedInterpolation [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-01-31 23:30:06,306 INFO L138 SettingsManager]: * Use separate solver for trace checks=false 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-01-31 23:30:06,483 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-01-31 23:30:06,505 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-01-31 23:30:06,508 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-01-31 23:30:06,509 INFO L271 PluginConnector]: Initializing CDTParser... [2022-01-31 23:30:06,509 INFO L275 PluginConnector]: CDTParser initialized [2022-01-31 23:30:06,510 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/verifythis/tree_del_iter_incorrect.c [2022-01-31 23:30:06,550 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/45002e384/613ad3a66bce46a188e93071b0617e70/FLAGc3bfa1590 [2022-01-31 23:30:06,867 INFO L306 CDTParser]: Found 1 translation units. [2022-01-31 23:30:06,868 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/verifythis/tree_del_iter_incorrect.c [2022-01-31 23:30:06,875 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/45002e384/613ad3a66bce46a188e93071b0617e70/FLAGc3bfa1590 [2022-01-31 23:30:07,287 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/45002e384/613ad3a66bce46a188e93071b0617e70 [2022-01-31 23:30:07,289 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-01-31 23:30:07,290 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-01-31 23:30:07,293 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-01-31 23:30:07,293 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-01-31 23:30:07,296 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-01-31 23:30:07,297 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,298 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@26803198 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07, skipping insertion in model container [2022-01-31 23:30:07,298 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,303 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-01-31 23:30:07,318 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-01-31 23:30:07,485 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/verifythis/tree_del_iter_incorrect.c[619,632] [2022-01-31 23:30:07,525 WARN L1533 CHandler]: Possible shadowing of function min [2022-01-31 23:30:07,535 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-31 23:30:07,541 INFO L203 MainTranslator]: Completed pre-run [2022-01-31 23:30:07,549 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/verifythis/tree_del_iter_incorrect.c[619,632] [2022-01-31 23:30:07,553 WARN L1533 CHandler]: Possible shadowing of function min [2022-01-31 23:30:07,558 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-31 23:30:07,568 INFO L208 MainTranslator]: Completed translation [2022-01-31 23:30:07,569 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07 WrapperNode [2022-01-31 23:30:07,569 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-01-31 23:30:07,569 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-01-31 23:30:07,570 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-01-31 23:30:07,570 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-01-31 23:30:07,587 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,588 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,607 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,607 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,626 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,629 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,631 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,633 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-01-31 23:30:07,633 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-01-31 23:30:07,633 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-01-31 23:30:07,634 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-01-31 23:30:07,634 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (1/1) ... [2022-01-31 23:30:07,639 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-31 23:30:07,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 23:30:07,662 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) [2022-01-31 23:30:07,680 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 [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_tree [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure min [2022-01-31 23:30:07,686 INFO L138 BoogieDeclarations]: Found implementation of procedure tree_del [2022-01-31 23:30:07,687 INFO L138 BoogieDeclarations]: Found implementation of procedure tree_inorder [2022-01-31 23:30:07,687 INFO L138 BoogieDeclarations]: Found implementation of procedure size [2022-01-31 23:30:07,687 INFO L138 BoogieDeclarations]: Found implementation of procedure task [2022-01-31 23:30:07,687 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-01-31 23:30:07,687 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.meminit [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure calloc [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure malloc [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure free [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_bool [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-01-31 23:30:07,687 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_tree [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure min [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure tree_del [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-01-31 23:30:07,688 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure tree_inorder [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure size [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure task [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.meminit [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-01-31 23:30:07,689 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-01-31 23:30:07,755 INFO L234 CfgBuilder]: Building ICFG [2022-01-31 23:30:07,756 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-01-31 23:30:08,005 INFO L275 CfgBuilder]: Performing block encoding [2022-01-31 23:30:08,010 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-01-31 23:30:08,010 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-01-31 23:30:08,011 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 11:30:08 BoogieIcfgContainer [2022-01-31 23:30:08,011 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-01-31 23:30:08,012 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-01-31 23:30:08,012 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-01-31 23:30:08,015 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-01-31 23:30:08,016 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.01 11:30:07" (1/3) ... [2022-01-31 23:30:08,016 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3edf49ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 11:30:08, skipping insertion in model container [2022-01-31 23:30:08,016 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 11:30:07" (2/3) ... [2022-01-31 23:30:08,017 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3edf49ca and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 11:30:08, skipping insertion in model container [2022-01-31 23:30:08,017 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 11:30:08" (3/3) ... [2022-01-31 23:30:08,018 INFO L111 eAbstractionObserver]: Analyzing ICFG tree_del_iter_incorrect.c [2022-01-31 23:30:08,022 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:AcceleratedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-01-31 23:30:08,022 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-01-31 23:30:08,056 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-01-31 23:30:08,061 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=AcceleratedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, 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=QVASR [2022-01-31 23:30:08,061 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-01-31 23:30:08,079 INFO L276 IsEmpty]: Start isEmpty. Operand has 96 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 59 states have internal predecessors, (71), 25 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) [2022-01-31 23:30:08,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-01-31 23:30:08,088 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:08,089 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 23:30:08,089 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:08,093 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:08,093 INFO L85 PathProgramCache]: Analyzing trace with hash 1536185801, now seen corresponding path program 1 times [2022-01-31 23:30:08,098 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:08,098 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [153825885] [2022-01-31 23:30:08,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:08,108 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:08,141 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:08,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,263 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 23:30:08,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,286 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-31 23:30:08,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,301 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-01-31 23:30:08,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,309 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-01-31 23:30:08,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,313 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2022-01-31 23:30:08,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,325 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-01-31 23:30:08,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,341 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2022-01-31 23:30:08,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,357 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 23:30:08,358 INFO L139 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2022-01-31 23:30:08,358 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [153825885] [2022-01-31 23:30:08,359 INFO L160 FreeRefinementEngine]: IpTcStrategyModulePreferences [153825885] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 23:30:08,359 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 23:30:08,360 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-01-31 23:30:08,360 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1462151423] [2022-01-31 23:30:08,361 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 23:30:08,363 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-31 23:30:08,363 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2022-01-31 23:30:08,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-31 23:30:08,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-01-31 23:30:08,387 INFO L87 Difference]: Start difference. First operand has 96 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 59 states have internal predecessors, (71), 25 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) Second operand has 6 states, 6 states have (on average 4.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (10), 6 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-01-31 23:30:08,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 23:30:08,659 INFO L93 Difference]: Finished difference Result 168 states and 221 transitions. [2022-01-31 23:30:08,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-31 23:30:08,661 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (10), 6 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-01-31 23:30:08,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 23:30:08,667 INFO L225 Difference]: With dead ends: 168 [2022-01-31 23:30:08,667 INFO L226 Difference]: Without dead ends: 95 [2022-01-31 23:30:08,669 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2022-01-31 23:30:08,671 INFO L933 BasicCegarLoop]: 78 mSDtfsCounter, 167 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 154 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 185 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 252 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 154 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-01-31 23:30:08,672 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [185 Valid, 80 Invalid, 252 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [154 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-01-31 23:30:08,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-01-31 23:30:08,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 88. [2022-01-31 23:30:08,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 53 states have (on average 1.150943396226415) internal successors, (61), 53 states have internal predecessors, (61), 25 states have call successors, (25), 11 states have call predecessors, (25), 9 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-01-31 23:30:08,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 109 transitions. [2022-01-31 23:30:08,703 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 109 transitions. Word has length 44 [2022-01-31 23:30:08,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 23:30:08,704 INFO L470 AbstractCegarLoop]: Abstraction has 88 states and 109 transitions. [2022-01-31 23:30:08,704 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.5) internal successors, (27), 2 states have internal predecessors, (27), 2 states have call successors, (10), 6 states have call predecessors, (10), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-01-31 23:30:08,704 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 109 transitions. [2022-01-31 23:30:08,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-01-31 23:30:08,705 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:08,706 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 23:30:08,706 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-01-31 23:30:08,706 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:08,706 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:08,706 INFO L85 PathProgramCache]: Analyzing trace with hash -152757941, now seen corresponding path program 1 times [2022-01-31 23:30:08,707 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:08,707 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [782607412] [2022-01-31 23:30:08,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:08,707 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:08,709 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:08,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,757 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 23:30:08,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,769 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-31 23:30:08,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,772 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-01-31 23:30:08,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,775 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-01-31 23:30:08,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,784 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2022-01-31 23:30:08,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,806 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-01-31 23:30:08,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,819 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2022-01-31 23:30:08,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:08,822 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 23:30:08,822 INFO L139 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2022-01-31 23:30:08,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [782607412] [2022-01-31 23:30:08,823 INFO L160 FreeRefinementEngine]: IpTcStrategyModulePreferences [782607412] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 23:30:08,823 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 23:30:08,823 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-01-31 23:30:08,823 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650751102] [2022-01-31 23:30:08,823 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 23:30:08,824 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-01-31 23:30:08,824 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2022-01-31 23:30:08,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-01-31 23:30:08,824 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-01-31 23:30:08,824 INFO L87 Difference]: Start difference. First operand 88 states and 109 transitions. Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-01-31 23:30:09,292 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 23:30:09,292 INFO L93 Difference]: Finished difference Result 154 states and 197 transitions. [2022-01-31 23:30:09,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-01-31 23:30:09,293 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 44 [2022-01-31 23:30:09,293 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 23:30:09,294 INFO L225 Difference]: With dead ends: 154 [2022-01-31 23:30:09,294 INFO L226 Difference]: Without dead ends: 97 [2022-01-31 23:30:09,295 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=77, Invalid=229, Unknown=0, NotChecked=0, Total=306 [2022-01-31 23:30:09,296 INFO L933 BasicCegarLoop]: 69 mSDtfsCounter, 98 mSDsluCounter, 10 mSDsCounter, 0 mSdLazyCounter, 658 mSolverCounterSat, 99 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 757 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 99 IncrementalHoareTripleChecker+Valid, 658 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-01-31 23:30:09,296 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [116 Valid, 79 Invalid, 757 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [99 Valid, 658 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-01-31 23:30:09,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2022-01-31 23:30:09,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 90. [2022-01-31 23:30:09,307 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 54 states have (on average 1.1481481481481481) internal successors, (62), 55 states have internal predecessors, (62), 25 states have call successors, (25), 11 states have call predecessors, (25), 10 states have return successors, (26), 23 states have call predecessors, (26), 23 states have call successors, (26) [2022-01-31 23:30:09,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 113 transitions. [2022-01-31 23:30:09,308 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 113 transitions. Word has length 44 [2022-01-31 23:30:09,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 23:30:09,309 INFO L470 AbstractCegarLoop]: Abstraction has 90 states and 113 transitions. [2022-01-31 23:30:09,309 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 6 states have internal predecessors, (27), 3 states have call successors, (10), 6 states have call predecessors, (10), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2022-01-31 23:30:09,309 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 113 transitions. [2022-01-31 23:30:09,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-01-31 23:30:09,310 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:09,310 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 23:30:09,311 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-01-31 23:30:09,311 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:09,311 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:09,311 INFO L85 PathProgramCache]: Analyzing trace with hash 2001282500, now seen corresponding path program 1 times [2022-01-31 23:30:09,311 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:09,311 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [8741653] [2022-01-31 23:30:09,311 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:09,312 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:09,313 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:09,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,377 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 23:30:09,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,398 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-31 23:30:09,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,443 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-01-31 23:30:09,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,464 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-01-31 23:30:09,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,540 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-01-31 23:30:09,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,544 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-01-31 23:30:09,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,547 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2022-01-31 23:30:09,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,556 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2022-01-31 23:30:09,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,593 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2022-01-31 23:30:09,595 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:09,597 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-01-31 23:30:09,598 INFO L139 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2022-01-31 23:30:09,598 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [8741653] [2022-01-31 23:30:09,598 INFO L160 FreeRefinementEngine]: IpTcStrategyModulePreferences [8741653] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 23:30:09,598 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 23:30:09,598 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-01-31 23:30:09,598 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515248047] [2022-01-31 23:30:09,598 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 23:30:09,598 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-01-31 23:30:09,599 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2022-01-31 23:30:09,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-01-31 23:30:09,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2022-01-31 23:30:09,599 INFO L87 Difference]: Start difference. First operand 90 states and 113 transitions. Second operand has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 7 states have internal predecessors, (32), 6 states have call successors, (12), 7 states have call predecessors, (12), 3 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2022-01-31 23:30:10,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 23:30:10,196 INFO L93 Difference]: Finished difference Result 164 states and 209 transitions. [2022-01-31 23:30:10,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-01-31 23:30:10,196 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 7 states have internal predecessors, (32), 6 states have call successors, (12), 7 states have call predecessors, (12), 3 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) Word has length 56 [2022-01-31 23:30:10,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 23:30:10,198 INFO L225 Difference]: With dead ends: 164 [2022-01-31 23:30:10,198 INFO L226 Difference]: Without dead ends: 96 [2022-01-31 23:30:10,199 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=107, Invalid=355, Unknown=0, NotChecked=0, Total=462 [2022-01-31 23:30:10,199 INFO L933 BasicCegarLoop]: 70 mSDtfsCounter, 175 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 848 mSolverCounterSat, 175 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 192 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 1023 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 175 IncrementalHoareTripleChecker+Valid, 848 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-01-31 23:30:10,200 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [192 Valid, 84 Invalid, 1023 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [175 Valid, 848 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-01-31 23:30:10,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-01-31 23:30:10,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 92. [2022-01-31 23:30:10,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 55 states have (on average 1.1454545454545455) internal successors, (63), 57 states have internal predecessors, (63), 25 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (28), 23 states have call predecessors, (28), 23 states have call successors, (28) [2022-01-31 23:30:10,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 116 transitions. [2022-01-31 23:30:10,210 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 116 transitions. Word has length 56 [2022-01-31 23:30:10,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 23:30:10,211 INFO L470 AbstractCegarLoop]: Abstraction has 92 states and 116 transitions. [2022-01-31 23:30:10,211 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 7 states have internal predecessors, (32), 6 states have call successors, (12), 7 states have call predecessors, (12), 3 states have return successors, (9), 6 states have call predecessors, (9), 5 states have call successors, (9) [2022-01-31 23:30:10,211 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 116 transitions. [2022-01-31 23:30:10,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2022-01-31 23:30:10,212 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:10,212 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 23:30:10,212 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-01-31 23:30:10,212 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:10,213 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:10,213 INFO L85 PathProgramCache]: Analyzing trace with hash 921875361, now seen corresponding path program 1 times [2022-01-31 23:30:10,213 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:10,213 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1939010866] [2022-01-31 23:30:10,213 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:10,213 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:10,214 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:10,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,251 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 23:30:10,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,262 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-31 23:30:10,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,284 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2022-01-31 23:30:10,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,287 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-01-31 23:30:10,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,291 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-01-31 23:30:10,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,305 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2022-01-31 23:30:10,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,310 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-01-31 23:30:10,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,312 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-01-31 23:30:10,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,314 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 45 [2022-01-31 23:30:10,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,322 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2022-01-31 23:30:10,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,334 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2022-01-31 23:30:10,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,337 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-01-31 23:30:10,337 INFO L139 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2022-01-31 23:30:10,337 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1939010866] [2022-01-31 23:30:10,337 INFO L160 FreeRefinementEngine]: IpTcStrategyModulePreferences [1939010866] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 23:30:10,337 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 23:30:10,337 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-01-31 23:30:10,338 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1912052329] [2022-01-31 23:30:10,338 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 23:30:10,338 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-01-31 23:30:10,338 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2022-01-31 23:30:10,338 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-01-31 23:30:10,338 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2022-01-31 23:30:10,339 INFO L87 Difference]: Start difference. First operand 92 states and 116 transitions. Second operand has 13 states, 11 states have (on average 3.090909090909091) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (14), 7 states have call predecessors, (14), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-01-31 23:30:10,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 23:30:10,869 INFO L93 Difference]: Finished difference Result 163 states and 208 transitions. [2022-01-31 23:30:10,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-01-31 23:30:10,870 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 3.090909090909091) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (14), 7 states have call predecessors, (14), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 66 [2022-01-31 23:30:10,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 23:30:10,871 INFO L225 Difference]: With dead ends: 163 [2022-01-31 23:30:10,871 INFO L226 Difference]: Without dead ends: 98 [2022-01-31 23:30:10,872 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2022-01-31 23:30:10,873 INFO L933 BasicCegarLoop]: 68 mSDtfsCounter, 168 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 826 mSolverCounterSat, 164 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 170 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 990 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 164 IncrementalHoareTripleChecker+Valid, 826 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-01-31 23:30:10,873 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [170 Valid, 82 Invalid, 990 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [164 Valid, 826 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-01-31 23:30:10,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-01-31 23:30:10,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 94. [2022-01-31 23:30:10,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 56 states have (on average 1.1428571428571428) internal successors, (64), 59 states have internal predecessors, (64), 25 states have call successors, (25), 11 states have call predecessors, (25), 12 states have return successors, (30), 23 states have call predecessors, (30), 23 states have call successors, (30) [2022-01-31 23:30:10,883 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 119 transitions. [2022-01-31 23:30:10,883 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 119 transitions. Word has length 66 [2022-01-31 23:30:10,883 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 23:30:10,883 INFO L470 AbstractCegarLoop]: Abstraction has 94 states and 119 transitions. [2022-01-31 23:30:10,883 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 3.090909090909091) internal successors, (34), 7 states have internal predecessors, (34), 5 states have call successors, (14), 7 states have call predecessors, (14), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-01-31 23:30:10,883 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 119 transitions. [2022-01-31 23:30:10,884 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-01-31 23:30:10,884 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:10,884 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 23:30:10,884 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-01-31 23:30:10,884 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:10,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:10,885 INFO L85 PathProgramCache]: Analyzing trace with hash 940648973, now seen corresponding path program 1 times [2022-01-31 23:30:10,885 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:10,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [192552276] [2022-01-31 23:30:10,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:10,885 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:10,886 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:10,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,925 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 23:30:10,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,935 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2022-01-31 23:30:10,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,956 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2022-01-31 23:30:10,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-01-31 23:30:10,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,961 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-01-31 23:30:10,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,965 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-01-31 23:30:10,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,967 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-01-31 23:30:10,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,969 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2022-01-31 23:30:10,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,973 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-01-31 23:30:10,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,975 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2022-01-31 23:30:10,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,977 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2022-01-31 23:30:10,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,984 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2022-01-31 23:30:10,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:10,994 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2022-01-31 23:30:10,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 23:30:11,010 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-01-31 23:30:11,010 INFO L139 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2022-01-31 23:30:11,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [192552276] [2022-01-31 23:30:11,010 INFO L160 FreeRefinementEngine]: IpTcStrategyModulePreferences [192552276] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 23:30:11,010 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 23:30:11,010 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-01-31 23:30:11,010 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [552912076] [2022-01-31 23:30:11,011 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 23:30:11,011 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-01-31 23:30:11,011 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2022-01-31 23:30:11,011 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-01-31 23:30:11,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=130, Unknown=0, NotChecked=0, Total=156 [2022-01-31 23:30:11,012 INFO L87 Difference]: Start difference. First operand 94 states and 119 transitions. Second operand has 13 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 7 states have internal predecessors, (38), 5 states have call successors, (16), 7 states have call predecessors, (16), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2022-01-31 23:30:11,502 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 23:30:11,502 INFO L93 Difference]: Finished difference Result 151 states and 192 transitions. [2022-01-31 23:30:11,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-01-31 23:30:11,502 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 7 states have internal predecessors, (38), 5 states have call successors, (16), 7 states have call predecessors, (16), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) Word has length 79 [2022-01-31 23:30:11,503 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 23:30:11,503 INFO L225 Difference]: With dead ends: 151 [2022-01-31 23:30:11,504 INFO L226 Difference]: Without dead ends: 98 [2022-01-31 23:30:11,504 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=114, Invalid=486, Unknown=0, NotChecked=0, Total=600 [2022-01-31 23:30:11,505 INFO L933 BasicCegarLoop]: 68 mSDtfsCounter, 196 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 786 mSolverCounterSat, 187 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 196 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 973 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 187 IncrementalHoareTripleChecker+Valid, 786 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-01-31 23:30:11,505 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [196 Valid, 82 Invalid, 973 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [187 Valid, 786 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-01-31 23:30:11,505 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-01-31 23:30:11,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 96. [2022-01-31 23:30:11,513 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 57 states have (on average 1.1403508771929824) internal successors, (65), 61 states have internal predecessors, (65), 25 states have call successors, (25), 11 states have call predecessors, (25), 13 states have return successors, (33), 23 states have call predecessors, (33), 23 states have call successors, (33) [2022-01-31 23:30:11,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 123 transitions. [2022-01-31 23:30:11,514 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 123 transitions. Word has length 79 [2022-01-31 23:30:11,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 23:30:11,514 INFO L470 AbstractCegarLoop]: Abstraction has 96 states and 123 transitions. [2022-01-31 23:30:11,514 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 7 states have internal predecessors, (38), 5 states have call successors, (16), 7 states have call predecessors, (16), 3 states have return successors, (13), 5 states have call predecessors, (13), 3 states have call successors, (13) [2022-01-31 23:30:11,515 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 123 transitions. [2022-01-31 23:30:11,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-01-31 23:30:11,515 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 23:30:11,516 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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] [2022-01-31 23:30:11,516 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2022-01-31 23:30:11,516 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 23:30:11,516 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 23:30:11,516 INFO L85 PathProgramCache]: Analyzing trace with hash 1677199096, now seen corresponding path program 1 times [2022-01-31 23:30:11,516 INFO L121 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2022-01-31 23:30:11,516 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [620164420] [2022-01-31 23:30:11,516 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 23:30:11,517 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 23:30:11,518 INFO L248 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-01-31 23:30:11,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-01-31 23:30:11,539 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-01-31 23:30:11,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-01-31 23:30:11,596 INFO L133 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found a feasible trace [2022-01-31 23:30:11,596 INFO L628 BasicCegarLoop]: Counterexample is feasible [2022-01-31 23:30:11,598 INFO L764 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-01-31 23:30:11,599 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2022-01-31 23:30:11,601 INFO L732 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1] [2022-01-31 23:30:11,602 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-01-31 23:30:11,612 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 31.01 11:30:11 BoogieIcfgContainer [2022-01-31 23:30:11,612 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-01-31 23:30:11,613 INFO L158 Benchmark]: Toolchain (without parser) took 4323.05ms. Allocated memory was 194.0MB in the beginning and 234.9MB in the end (delta: 40.9MB). Free memory was 144.6MB in the beginning and 207.9MB in the end (delta: -63.4MB). Peak memory consumption was 109.0MB. Max. memory is 8.0GB. [2022-01-31 23:30:11,613 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 194.0MB. Free memory was 161.4MB in the beginning and 161.3MB in the end (delta: 72.5kB). There was no memory consumed. Max. memory is 8.0GB. [2022-01-31 23:30:11,613 INFO L158 Benchmark]: CACSL2BoogieTranslator took 275.79ms. Allocated memory is still 194.0MB. Free memory was 144.3MB in the beginning and 168.8MB in the end (delta: -24.4MB). Peak memory consumption was 10.8MB. Max. memory is 8.0GB. [2022-01-31 23:30:11,613 INFO L158 Benchmark]: Boogie Preprocessor took 63.38ms. Allocated memory is still 194.0MB. Free memory was 168.8MB in the beginning and 166.7MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-01-31 23:30:11,613 INFO L158 Benchmark]: RCFGBuilder took 378.14ms. Allocated memory is still 194.0MB. Free memory was 166.7MB in the beginning and 147.2MB in the end (delta: 19.4MB). Peak memory consumption was 19.9MB. Max. memory is 8.0GB. [2022-01-31 23:30:11,614 INFO L158 Benchmark]: TraceAbstraction took 3599.95ms. Allocated memory was 194.0MB in the beginning and 234.9MB in the end (delta: 40.9MB). Free memory was 146.8MB in the beginning and 207.9MB in the end (delta: -61.2MB). Peak memory consumption was 111.8MB. Max. memory is 8.0GB. [2022-01-31 23:30:11,614 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.09ms. Allocated memory is still 194.0MB. Free memory was 161.4MB in the beginning and 161.3MB in the end (delta: 72.5kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 275.79ms. Allocated memory is still 194.0MB. Free memory was 144.3MB in the beginning and 168.8MB in the end (delta: -24.4MB). Peak memory consumption was 10.8MB. Max. memory is 8.0GB. * Boogie Preprocessor took 63.38ms. Allocated memory is still 194.0MB. Free memory was 168.8MB in the beginning and 166.7MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 378.14ms. Allocated memory is still 194.0MB. Free memory was 166.7MB in the beginning and 147.2MB in the end (delta: 19.4MB). Peak memory consumption was 19.9MB. Max. memory is 8.0GB. * TraceAbstraction took 3599.95ms. Allocated memory was 194.0MB in the beginning and 234.9MB in the end (delta: 40.9MB). Free memory was 146.8MB in the beginning and 207.9MB in the end (delta: -61.2MB). Peak memory consumption was 111.8MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 16]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L105] CALL, EXPR nondet_tree() [L25] COND FALSE !(__VERIFIER_nondet_bool()) [L28] struct node *n = (struct node *)malloc(sizeof(struct node)); [L29] n->data = __VERIFIER_nondet_int() [L30] CALL, EXPR nondet_tree() [L25] COND TRUE __VERIFIER_nondet_bool() [L26] return 0; [L30] RET, EXPR nondet_tree() [L30] n->left = nondet_tree() [L31] CALL, EXPR nondet_tree() [L25] COND TRUE __VERIFIER_nondet_bool() [L26] return 0; [L31] RET, EXPR nondet_tree() [L31] n->right = nondet_tree() [L32] return n; [L105] RET, EXPR nondet_tree() [L105] CALL task(nondet_tree()) [L83] CALL, EXPR min(t) [L37] COND FALSE !(!n) [L40] EXPR n->left [L40] CALL, EXPR min(n->left) [L37] COND TRUE !n [L38] return 2147483647; [L40] RET, EXPR min(n->left) [L40] int a = min(n->left); [L41] EXPR n->right [L41] CALL, EXPR min(n->right) [L37] COND TRUE !n [L38] return 2147483647; [L41] RET, EXPR min(n->right) [L41] int b = min(n->right); [L42] COND TRUE a <= b [L42] return a; [L83] RET, EXPR min(t) [L83] int a = min(t); [L84] int b; [L86] CALL, EXPR size(t) [L78] COND FALSE !(!t) [L79] EXPR t->left [L79] CALL, EXPR size(t->left) [L78] COND TRUE !t [L78] return 0; [L79] RET, EXPR size(t->left) [L79] EXPR t->right [L79] CALL, EXPR size(t->right) [L78] COND TRUE !t [L78] return 0; [L79] RET, EXPR size(t->right) [L79] return size(t->left) + size(t->right) + 1; [L86] RET, EXPR size(t) [L86] int n = size(t); [L87] CALL assume_abort_if_not(n != 0) [L10] COND FALSE !(!cond) [L87] RET assume_abort_if_not(n != 0) [L88] EXPR, FCALL calloc(n, sizeof(int)) [L88] int *x = calloc(n, sizeof(int)); [L89] CALL tree_inorder(t, x, n) [L67] COND FALSE !(!t) [L70] EXPR t->left [L70] CALL, EXPR tree_inorder(t->left, a, i) [L67] COND TRUE !t [L68] return i; [L70] RET, EXPR tree_inorder(t->left, a, i) [L70] i = tree_inorder(t->left, a, i) [L71] EXPR i++ [L71] EXPR t->data [L71] a[i++] = t->data [L72] EXPR t->right [L72] CALL, EXPR tree_inorder(t->right, a, i) [L67] COND TRUE !t [L68] return i; [L72] RET, EXPR tree_inorder(t->right, a, i) [L72] i = tree_inorder(t->right, a, i) [L73] return i; [L89] RET tree_inorder(t, x, n) [L90] EXPR x[0] [L90] CALL __VERIFIER_assert(a == x[0]) [L16] COND TRUE !cond [L16] reach_error() - StatisticsResult: Ultimate Automizer benchmark data CFG has 13 procedures, 99 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 3.5s, OverallIterations: 6, TraceHistogramMax: 3, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 2.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 859 SdHoareTripleChecker+Valid, 1.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 804 mSDsluCounter, 407 SdHoareTripleChecker+Invalid, 1.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 54 mSDsCounter, 779 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3216 IncrementalHoareTripleChecker+Invalid, 3995 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 779 mSolverCounterUnsat, 353 mSDtfsCounter, 3216 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 175 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 183 ImplicationChecksByTransitivity, 0.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=96occurred in iteration=0, InterpolantAutomatonStates: 61, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 5 MinimizatonAttempts, 24 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-01-31 23:30:11,637 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...