java -ea -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline_WitnessPrinter.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/list-simple/dll2c_update_all_reverse_true-unreach-call_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-61f4311 [2018-11-23 12:56:36,146 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-23 12:56:36,148 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-23 12:56:36,164 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-23 12:56:36,165 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-23 12:56:36,166 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-23 12:56:36,167 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-23 12:56:36,169 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-23 12:56:36,171 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-23 12:56:36,172 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-23 12:56:36,172 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-23 12:56:36,173 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-23 12:56:36,174 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-23 12:56:36,175 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-23 12:56:36,176 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-23 12:56:36,177 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-23 12:56:36,178 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-23 12:56:36,180 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-23 12:56:36,182 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-23 12:56:36,184 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-23 12:56:36,185 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-23 12:56:36,187 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-23 12:56:36,189 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-23 12:56:36,189 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-23 12:56:36,190 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-23 12:56:36,191 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-23 12:56:36,192 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-23 12:56:36,193 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-23 12:56:36,194 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-23 12:56:36,195 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-23 12:56:36,195 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-23 12:56:36,196 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-23 12:56:36,196 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-23 12:56:36,196 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-23 12:56:36,197 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-23 12:56:36,198 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-23 12:56:36,198 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2018-11-23 12:56:36,221 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-23 12:56:36,222 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-23 12:56:36,223 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-23 12:56:36,223 INFO L133 SettingsManager]: * ... calls to implemented procedures=ONLY_FOR_CONCURRENT_PROGRAMS [2018-11-23 12:56:36,224 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-11-23 12:56:36,224 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-11-23 12:56:36,224 INFO L133 SettingsManager]: * Use SBE=true [2018-11-23 12:56:36,226 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-23 12:56:36,226 INFO L133 SettingsManager]: * sizeof long=4 [2018-11-23 12:56:36,226 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-23 12:56:36,226 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-11-23 12:56:36,227 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-23 12:56:36,227 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-23 12:56:36,227 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-23 12:56:36,227 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-23 12:56:36,228 INFO L133 SettingsManager]: * sizeof long double=12 [2018-11-23 12:56:36,228 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-23 12:56:36,228 INFO L133 SettingsManager]: * Use constant arrays=true [2018-11-23 12:56:36,228 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-23 12:56:36,228 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-23 12:56:36,229 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-23 12:56:36,229 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-23 12:56:36,229 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-23 12:56:36,229 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-23 12:56:36,229 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-23 12:56:36,231 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-23 12:56:36,231 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-23 12:56:36,231 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-11-23 12:56:36,232 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-23 12:56:36,232 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-23 12:56:36,232 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-23 12:56:36,296 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-23 12:56:36,309 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-23 12:56:36,313 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-23 12:56:36,314 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-23 12:56:36,314 INFO L276 PluginConnector]: CDTParser initialized [2018-11-23 12:56:36,315 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/list-simple/dll2c_update_all_reverse_true-unreach-call_true-valid-memsafety.i [2018-11-23 12:56:36,391 INFO L221 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8d75ab369/c0a4430caa554feb9e091e9b39451447/FLAGdeb4ba5c6 [2018-11-23 12:56:36,915 INFO L307 CDTParser]: Found 1 translation units. [2018-11-23 12:56:36,916 INFO L161 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/list-simple/dll2c_update_all_reverse_true-unreach-call_true-valid-memsafety.i [2018-11-23 12:56:36,931 INFO L355 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8d75ab369/c0a4430caa554feb9e091e9b39451447/FLAGdeb4ba5c6 [2018-11-23 12:56:37,204 INFO L363 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8d75ab369/c0a4430caa554feb9e091e9b39451447 [2018-11-23 12:56:37,214 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-23 12:56:37,215 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2018-11-23 12:56:37,219 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-23 12:56:37,219 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-23 12:56:37,227 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-23 12:56:37,229 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:37,233 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6a59a456 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37, skipping insertion in model container [2018-11-23 12:56:37,234 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:37,245 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-23 12:56:37,308 INFO L176 MainTranslator]: Built tables and reachable declarations [2018-11-23 12:56:37,749 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-23 12:56:37,761 INFO L191 MainTranslator]: Completed pre-run [2018-11-23 12:56:37,840 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-23 12:56:37,997 INFO L195 MainTranslator]: Completed translation [2018-11-23 12:56:37,997 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37 WrapperNode [2018-11-23 12:56:37,997 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-23 12:56:37,998 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-23 12:56:37,999 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-23 12:56:37,999 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-23 12:56:38,009 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,033 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,044 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-23 12:56:38,045 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-23 12:56:38,045 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-23 12:56:38,045 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-23 12:56:38,056 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,056 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,067 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,067 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,097 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,109 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,112 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... [2018-11-23 12:56:38,116 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-23 12:56:38,116 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-23 12:56:38,117 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-23 12:56:38,117 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-23 12:56:38,118 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-23 12:56:38,176 INFO L130 BoogieDeclarations]: Found specification of procedure dll_circular_update_at [2018-11-23 12:56:38,176 INFO L138 BoogieDeclarations]: Found implementation of procedure dll_circular_update_at [2018-11-23 12:56:38,177 INFO L130 BoogieDeclarations]: Found specification of procedure dll_circular_create [2018-11-23 12:56:38,177 INFO L138 BoogieDeclarations]: Found implementation of procedure dll_circular_create [2018-11-23 12:56:38,177 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-23 12:56:38,177 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-23 12:56:38,177 INFO L130 BoogieDeclarations]: Found specification of procedure dll_circular_get_data_at [2018-11-23 12:56:38,177 INFO L138 BoogieDeclarations]: Found implementation of procedure dll_circular_get_data_at [2018-11-23 12:56:38,178 INFO L130 BoogieDeclarations]: Found specification of procedure exit [2018-11-23 12:56:38,178 INFO L138 BoogieDeclarations]: Found implementation of procedure exit [2018-11-23 12:56:38,178 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-23 12:56:38,178 INFO L130 BoogieDeclarations]: Found specification of procedure node_create [2018-11-23 12:56:38,180 INFO L138 BoogieDeclarations]: Found implementation of procedure node_create [2018-11-23 12:56:38,180 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-23 12:56:38,180 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-23 12:56:38,181 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-23 12:56:38,181 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-23 12:56:38,181 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-11-23 12:56:38,181 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-11-23 12:56:38,181 INFO L130 BoogieDeclarations]: Found specification of procedure dll_circular_destroy [2018-11-23 12:56:38,181 INFO L138 BoogieDeclarations]: Found implementation of procedure dll_circular_destroy [2018-11-23 12:56:38,183 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-11-23 12:56:38,184 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-23 12:56:38,184 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-23 12:56:39,272 INFO L275 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-23 12:56:39,273 INFO L280 CfgBuilder]: Removed 6 assue(true) statements. [2018-11-23 12:56:39,273 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 12:56:39 BoogieIcfgContainer [2018-11-23 12:56:39,274 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-23 12:56:39,275 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-23 12:56:39,275 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-23 12:56:39,278 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-23 12:56:39,278 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 12:56:37" (1/3) ... [2018-11-23 12:56:39,280 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b9f27a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 12:56:39, skipping insertion in model container [2018-11-23 12:56:39,280 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 12:56:37" (2/3) ... [2018-11-23 12:56:39,281 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2b9f27a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 12:56:39, skipping insertion in model container [2018-11-23 12:56:39,281 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 12:56:39" (3/3) ... [2018-11-23 12:56:39,283 INFO L112 eAbstractionObserver]: Analyzing ICFG dll2c_update_all_reverse_true-unreach-call_true-valid-memsafety.i [2018-11-23 12:56:39,295 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-23 12:56:39,306 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-23 12:56:39,325 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-23 12:56:39,358 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-11-23 12:56:39,359 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-23 12:56:39,359 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-23 12:56:39,359 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-23 12:56:39,359 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-23 12:56:39,359 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-23 12:56:39,360 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-23 12:56:39,360 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-23 12:56:39,360 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-23 12:56:39,380 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-11-23 12:56:39,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-11-23 12:56:39,389 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:39,390 INFO L402 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] [2018-11-23 12:56:39,393 INFO L423 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:39,399 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:39,399 INFO L82 PathProgramCache]: Analyzing trace with hash -1670761163, now seen corresponding path program 1 times [2018-11-23 12:56:39,402 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:39,402 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:39,462 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:39,462 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:39,463 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:39,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:39,639 INFO L256 TraceCheckUtils]: 0: Hoare triple {63#true} call ULTIMATE.init(); {63#true} is VALID [2018-11-23 12:56:39,643 INFO L273 TraceCheckUtils]: 1: Hoare triple {63#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {63#true} is VALID [2018-11-23 12:56:39,643 INFO L273 TraceCheckUtils]: 2: Hoare triple {63#true} assume true; {63#true} is VALID [2018-11-23 12:56:39,644 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {63#true} {63#true} #153#return; {63#true} is VALID [2018-11-23 12:56:39,644 INFO L256 TraceCheckUtils]: 4: Hoare triple {63#true} call #t~ret17 := main(); {63#true} is VALID [2018-11-23 12:56:39,645 INFO L273 TraceCheckUtils]: 5: Hoare triple {63#true} ~len~0 := 2;~data~0 := 1; {63#true} is VALID [2018-11-23 12:56:39,645 INFO L256 TraceCheckUtils]: 6: Hoare triple {63#true} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {63#true} is VALID [2018-11-23 12:56:39,645 INFO L273 TraceCheckUtils]: 7: Hoare triple {63#true} ~len := #in~len;~data := #in~data; {63#true} is VALID [2018-11-23 12:56:39,646 INFO L256 TraceCheckUtils]: 8: Hoare triple {63#true} call #t~ret3.base, #t~ret3.offset := node_create(~data); {63#true} is VALID [2018-11-23 12:56:39,646 INFO L273 TraceCheckUtils]: 9: Hoare triple {63#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {63#true} is VALID [2018-11-23 12:56:39,646 INFO L273 TraceCheckUtils]: 10: Hoare triple {63#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {63#true} is VALID [2018-11-23 12:56:39,647 INFO L273 TraceCheckUtils]: 11: Hoare triple {63#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {63#true} is VALID [2018-11-23 12:56:39,647 INFO L273 TraceCheckUtils]: 12: Hoare triple {63#true} assume true; {63#true} is VALID [2018-11-23 12:56:39,648 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {63#true} {63#true} #149#return; {63#true} is VALID [2018-11-23 12:56:39,648 INFO L273 TraceCheckUtils]: 14: Hoare triple {63#true} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {63#true} is VALID [2018-11-23 12:56:39,649 INFO L273 TraceCheckUtils]: 15: Hoare triple {63#true} assume !true; {64#false} is VALID [2018-11-23 12:56:39,649 INFO L273 TraceCheckUtils]: 16: Hoare triple {64#false} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {64#false} is VALID [2018-11-23 12:56:39,650 INFO L273 TraceCheckUtils]: 17: Hoare triple {64#false} assume true; {64#false} is VALID [2018-11-23 12:56:39,650 INFO L268 TraceCheckUtils]: 18: Hoare quadruple {64#false} {63#true} #141#return; {64#false} is VALID [2018-11-23 12:56:39,650 INFO L273 TraceCheckUtils]: 19: Hoare triple {64#false} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {64#false} is VALID [2018-11-23 12:56:39,651 INFO L273 TraceCheckUtils]: 20: Hoare triple {64#false} assume !(~i~0 > -1); {64#false} is VALID [2018-11-23 12:56:39,651 INFO L273 TraceCheckUtils]: 21: Hoare triple {64#false} ~i~0 := ~len~0 - 1; {64#false} is VALID [2018-11-23 12:56:39,651 INFO L273 TraceCheckUtils]: 22: Hoare triple {64#false} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {64#false} is VALID [2018-11-23 12:56:39,651 INFO L256 TraceCheckUtils]: 23: Hoare triple {64#false} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {63#true} is VALID [2018-11-23 12:56:39,652 INFO L273 TraceCheckUtils]: 24: Hoare triple {63#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {63#true} is VALID [2018-11-23 12:56:39,652 INFO L273 TraceCheckUtils]: 25: Hoare triple {63#true} assume !(~index > 0); {63#true} is VALID [2018-11-23 12:56:39,652 INFO L273 TraceCheckUtils]: 26: Hoare triple {63#true} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {63#true} is VALID [2018-11-23 12:56:39,652 INFO L273 TraceCheckUtils]: 27: Hoare triple {63#true} assume true; {63#true} is VALID [2018-11-23 12:56:39,653 INFO L268 TraceCheckUtils]: 28: Hoare quadruple {63#true} {64#false} #145#return; {64#false} is VALID [2018-11-23 12:56:39,653 INFO L273 TraceCheckUtils]: 29: Hoare triple {64#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {64#false} is VALID [2018-11-23 12:56:39,653 INFO L273 TraceCheckUtils]: 30: Hoare triple {64#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {64#false} is VALID [2018-11-23 12:56:39,654 INFO L273 TraceCheckUtils]: 31: Hoare triple {64#false} assume !false; {64#false} is VALID [2018-11-23 12:56:39,661 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-23 12:56:39,664 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-23 12:56:39,664 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-23 12:56:39,669 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 32 [2018-11-23 12:56:39,673 INFO L84 Accepts]: Finished accepts. word is accepted. [2018-11-23 12:56:39,677 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 2 states. [2018-11-23 12:56:39,768 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 32 edges. 32 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:39,769 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-23 12:56:39,778 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-23 12:56:39,779 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-23 12:56:39,782 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 2 states. [2018-11-23 12:56:40,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:40,401 INFO L93 Difference]: Finished difference Result 97 states and 127 transitions. [2018-11-23 12:56:40,401 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-23 12:56:40,401 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 32 [2018-11-23 12:56:40,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-23 12:56:40,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2 states. [2018-11-23 12:56:40,417 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2 states to 2 states and 127 transitions. [2018-11-23 12:56:40,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2 states. [2018-11-23 12:56:40,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2 states to 2 states and 127 transitions. [2018-11-23 12:56:40,425 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 2 states and 127 transitions. [2018-11-23 12:56:41,135 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 127 edges. 127 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:41,149 INFO L225 Difference]: With dead ends: 97 [2018-11-23 12:56:41,149 INFO L226 Difference]: Without dead ends: 45 [2018-11-23 12:56:41,153 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-23 12:56:41,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-11-23 12:56:41,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2018-11-23 12:56:41,205 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2018-11-23 12:56:41,206 INFO L82 GeneralOperation]: Start isEquivalent. First operand 45 states. Second operand 45 states. [2018-11-23 12:56:41,206 INFO L74 IsIncluded]: Start isIncluded. First operand 45 states. Second operand 45 states. [2018-11-23 12:56:41,207 INFO L87 Difference]: Start difference. First operand 45 states. Second operand 45 states. [2018-11-23 12:56:41,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:41,214 INFO L93 Difference]: Finished difference Result 45 states and 51 transitions. [2018-11-23 12:56:41,214 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2018-11-23 12:56:41,215 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:41,215 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:41,216 INFO L74 IsIncluded]: Start isIncluded. First operand 45 states. Second operand 45 states. [2018-11-23 12:56:41,216 INFO L87 Difference]: Start difference. First operand 45 states. Second operand 45 states. [2018-11-23 12:56:41,222 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:41,222 INFO L93 Difference]: Finished difference Result 45 states and 51 transitions. [2018-11-23 12:56:41,222 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2018-11-23 12:56:41,223 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:41,224 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:41,224 INFO L88 GeneralOperation]: Finished isEquivalent. [2018-11-23 12:56:41,224 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2018-11-23 12:56:41,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-11-23 12:56:41,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2018-11-23 12:56:41,230 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 32 [2018-11-23 12:56:41,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-23 12:56:41,231 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2018-11-23 12:56:41,231 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-23 12:56:41,232 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2018-11-23 12:56:41,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-11-23 12:56:41,233 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:41,233 INFO L402 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] [2018-11-23 12:56:41,234 INFO L423 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:41,234 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:41,234 INFO L82 PathProgramCache]: Analyzing trace with hash -2083918040, now seen corresponding path program 1 times [2018-11-23 12:56:41,234 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:41,235 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:41,236 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:41,237 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:41,237 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:41,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:41,408 INFO L256 TraceCheckUtils]: 0: Hoare triple {355#true} call ULTIMATE.init(); {355#true} is VALID [2018-11-23 12:56:41,409 INFO L273 TraceCheckUtils]: 1: Hoare triple {355#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {355#true} is VALID [2018-11-23 12:56:41,409 INFO L273 TraceCheckUtils]: 2: Hoare triple {355#true} assume true; {355#true} is VALID [2018-11-23 12:56:41,409 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {355#true} {355#true} #153#return; {355#true} is VALID [2018-11-23 12:56:41,410 INFO L256 TraceCheckUtils]: 4: Hoare triple {355#true} call #t~ret17 := main(); {355#true} is VALID [2018-11-23 12:56:41,410 INFO L273 TraceCheckUtils]: 5: Hoare triple {355#true} ~len~0 := 2;~data~0 := 1; {357#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:41,411 INFO L256 TraceCheckUtils]: 6: Hoare triple {357#(<= 2 main_~len~0)} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {355#true} is VALID [2018-11-23 12:56:41,411 INFO L273 TraceCheckUtils]: 7: Hoare triple {355#true} ~len := #in~len;~data := #in~data; {355#true} is VALID [2018-11-23 12:56:41,411 INFO L256 TraceCheckUtils]: 8: Hoare triple {355#true} call #t~ret3.base, #t~ret3.offset := node_create(~data); {355#true} is VALID [2018-11-23 12:56:41,412 INFO L273 TraceCheckUtils]: 9: Hoare triple {355#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {355#true} is VALID [2018-11-23 12:56:41,412 INFO L273 TraceCheckUtils]: 10: Hoare triple {355#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {355#true} is VALID [2018-11-23 12:56:41,412 INFO L273 TraceCheckUtils]: 11: Hoare triple {355#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {355#true} is VALID [2018-11-23 12:56:41,412 INFO L273 TraceCheckUtils]: 12: Hoare triple {355#true} assume true; {355#true} is VALID [2018-11-23 12:56:41,413 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {355#true} {355#true} #149#return; {355#true} is VALID [2018-11-23 12:56:41,413 INFO L273 TraceCheckUtils]: 14: Hoare triple {355#true} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {355#true} is VALID [2018-11-23 12:56:41,413 INFO L273 TraceCheckUtils]: 15: Hoare triple {355#true} assume !(~len > 1); {355#true} is VALID [2018-11-23 12:56:41,414 INFO L273 TraceCheckUtils]: 16: Hoare triple {355#true} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {355#true} is VALID [2018-11-23 12:56:41,415 INFO L273 TraceCheckUtils]: 17: Hoare triple {355#true} assume true; {355#true} is VALID [2018-11-23 12:56:41,420 INFO L268 TraceCheckUtils]: 18: Hoare quadruple {355#true} {357#(<= 2 main_~len~0)} #141#return; {357#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:41,422 INFO L273 TraceCheckUtils]: 19: Hoare triple {357#(<= 2 main_~len~0)} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {358#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:41,423 INFO L273 TraceCheckUtils]: 20: Hoare triple {358#(<= 1 main_~i~0)} assume !(~i~0 > -1); {356#false} is VALID [2018-11-23 12:56:41,423 INFO L273 TraceCheckUtils]: 21: Hoare triple {356#false} ~i~0 := ~len~0 - 1; {356#false} is VALID [2018-11-23 12:56:41,423 INFO L273 TraceCheckUtils]: 22: Hoare triple {356#false} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {356#false} is VALID [2018-11-23 12:56:41,424 INFO L256 TraceCheckUtils]: 23: Hoare triple {356#false} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {355#true} is VALID [2018-11-23 12:56:41,424 INFO L273 TraceCheckUtils]: 24: Hoare triple {355#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {355#true} is VALID [2018-11-23 12:56:41,425 INFO L273 TraceCheckUtils]: 25: Hoare triple {355#true} assume !(~index > 0); {355#true} is VALID [2018-11-23 12:56:41,425 INFO L273 TraceCheckUtils]: 26: Hoare triple {355#true} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {355#true} is VALID [2018-11-23 12:56:41,426 INFO L273 TraceCheckUtils]: 27: Hoare triple {355#true} assume true; {355#true} is VALID [2018-11-23 12:56:41,427 INFO L268 TraceCheckUtils]: 28: Hoare quadruple {355#true} {356#false} #145#return; {356#false} is VALID [2018-11-23 12:56:41,427 INFO L273 TraceCheckUtils]: 29: Hoare triple {356#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {356#false} is VALID [2018-11-23 12:56:41,428 INFO L273 TraceCheckUtils]: 30: Hoare triple {356#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {356#false} is VALID [2018-11-23 12:56:41,428 INFO L273 TraceCheckUtils]: 31: Hoare triple {356#false} assume !false; {356#false} is VALID [2018-11-23 12:56:41,430 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-23 12:56:41,431 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-23 12:56:41,431 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-11-23 12:56:41,433 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-11-23 12:56:41,433 INFO L84 Accepts]: Finished accepts. word is accepted. [2018-11-23 12:56:41,434 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 4 states. [2018-11-23 12:56:41,603 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 32 edges. 32 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:41,603 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-11-23 12:56:41,603 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-11-23 12:56:41,603 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-11-23 12:56:41,604 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand 4 states. [2018-11-23 12:56:41,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:41,973 INFO L93 Difference]: Finished difference Result 68 states and 78 transitions. [2018-11-23 12:56:41,973 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-11-23 12:56:41,974 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-11-23 12:56:41,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-23 12:56:41,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2018-11-23 12:56:41,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2018-11-23 12:56:41,979 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2018-11-23 12:56:41,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 78 transitions. [2018-11-23 12:56:41,983 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 4 states and 78 transitions. [2018-11-23 12:56:42,116 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 78 edges. 78 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:42,120 INFO L225 Difference]: With dead ends: 68 [2018-11-23 12:56:42,120 INFO L226 Difference]: Without dead ends: 55 [2018-11-23 12:56:42,121 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-11-23 12:56:42,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-11-23 12:56:42,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 46. [2018-11-23 12:56:42,161 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2018-11-23 12:56:42,162 INFO L82 GeneralOperation]: Start isEquivalent. First operand 55 states. Second operand 46 states. [2018-11-23 12:56:42,162 INFO L74 IsIncluded]: Start isIncluded. First operand 55 states. Second operand 46 states. [2018-11-23 12:56:42,162 INFO L87 Difference]: Start difference. First operand 55 states. Second operand 46 states. [2018-11-23 12:56:42,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:42,167 INFO L93 Difference]: Finished difference Result 55 states and 63 transitions. [2018-11-23 12:56:42,167 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 63 transitions. [2018-11-23 12:56:42,168 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:42,169 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:42,169 INFO L74 IsIncluded]: Start isIncluded. First operand 46 states. Second operand 55 states. [2018-11-23 12:56:42,169 INFO L87 Difference]: Start difference. First operand 46 states. Second operand 55 states. [2018-11-23 12:56:42,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:42,174 INFO L93 Difference]: Finished difference Result 55 states and 63 transitions. [2018-11-23 12:56:42,174 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 63 transitions. [2018-11-23 12:56:42,175 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:42,175 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:42,176 INFO L88 GeneralOperation]: Finished isEquivalent. [2018-11-23 12:56:42,176 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2018-11-23 12:56:42,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-11-23 12:56:42,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2018-11-23 12:56:42,180 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 32 [2018-11-23 12:56:42,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-23 12:56:42,180 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2018-11-23 12:56:42,180 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-11-23 12:56:42,180 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2018-11-23 12:56:42,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-11-23 12:56:42,182 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:42,182 INFO L402 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] [2018-11-23 12:56:42,183 INFO L423 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:42,183 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:42,183 INFO L82 PathProgramCache]: Analyzing trace with hash 133781746, now seen corresponding path program 1 times [2018-11-23 12:56:42,183 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:42,184 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:42,185 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:42,186 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:42,186 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:42,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:42,339 INFO L256 TraceCheckUtils]: 0: Hoare triple {636#true} call ULTIMATE.init(); {636#true} is VALID [2018-11-23 12:56:42,339 INFO L273 TraceCheckUtils]: 1: Hoare triple {636#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {636#true} is VALID [2018-11-23 12:56:42,340 INFO L273 TraceCheckUtils]: 2: Hoare triple {636#true} assume true; {636#true} is VALID [2018-11-23 12:56:42,340 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {636#true} {636#true} #153#return; {636#true} is VALID [2018-11-23 12:56:42,341 INFO L256 TraceCheckUtils]: 4: Hoare triple {636#true} call #t~ret17 := main(); {636#true} is VALID [2018-11-23 12:56:42,344 INFO L273 TraceCheckUtils]: 5: Hoare triple {636#true} ~len~0 := 2;~data~0 := 1; {638#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:42,345 INFO L256 TraceCheckUtils]: 6: Hoare triple {638#(<= 2 main_~len~0)} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {636#true} is VALID [2018-11-23 12:56:42,346 INFO L273 TraceCheckUtils]: 7: Hoare triple {636#true} ~len := #in~len;~data := #in~data; {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} is VALID [2018-11-23 12:56:42,346 INFO L256 TraceCheckUtils]: 8: Hoare triple {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} call #t~ret3.base, #t~ret3.offset := node_create(~data); {636#true} is VALID [2018-11-23 12:56:42,346 INFO L273 TraceCheckUtils]: 9: Hoare triple {636#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {636#true} is VALID [2018-11-23 12:56:42,347 INFO L273 TraceCheckUtils]: 10: Hoare triple {636#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {636#true} is VALID [2018-11-23 12:56:42,347 INFO L273 TraceCheckUtils]: 11: Hoare triple {636#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {636#true} is VALID [2018-11-23 12:56:42,347 INFO L273 TraceCheckUtils]: 12: Hoare triple {636#true} assume true; {636#true} is VALID [2018-11-23 12:56:42,352 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {636#true} {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} #149#return; {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} is VALID [2018-11-23 12:56:42,353 INFO L273 TraceCheckUtils]: 14: Hoare triple {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} is VALID [2018-11-23 12:56:42,361 INFO L273 TraceCheckUtils]: 15: Hoare triple {639#(<= |dll_circular_create_#in~len| dll_circular_create_~len)} assume !(~len > 1); {640#(<= |dll_circular_create_#in~len| 1)} is VALID [2018-11-23 12:56:42,362 INFO L273 TraceCheckUtils]: 16: Hoare triple {640#(<= |dll_circular_create_#in~len| 1)} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {640#(<= |dll_circular_create_#in~len| 1)} is VALID [2018-11-23 12:56:42,363 INFO L273 TraceCheckUtils]: 17: Hoare triple {640#(<= |dll_circular_create_#in~len| 1)} assume true; {640#(<= |dll_circular_create_#in~len| 1)} is VALID [2018-11-23 12:56:42,364 INFO L268 TraceCheckUtils]: 18: Hoare quadruple {640#(<= |dll_circular_create_#in~len| 1)} {638#(<= 2 main_~len~0)} #141#return; {637#false} is VALID [2018-11-23 12:56:42,364 INFO L273 TraceCheckUtils]: 19: Hoare triple {637#false} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {637#false} is VALID [2018-11-23 12:56:42,364 INFO L273 TraceCheckUtils]: 20: Hoare triple {637#false} assume !!(~i~0 > -1);~new_data~0 := ~i~0 + ~len~0; {637#false} is VALID [2018-11-23 12:56:42,365 INFO L256 TraceCheckUtils]: 21: Hoare triple {637#false} call dll_circular_update_at(~s~0.base, ~s~0.offset, ~new_data~0, ~i~0); {636#true} is VALID [2018-11-23 12:56:42,365 INFO L273 TraceCheckUtils]: 22: Hoare triple {636#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~data := #in~data;~index := #in~index; {636#true} is VALID [2018-11-23 12:56:42,366 INFO L273 TraceCheckUtils]: 23: Hoare triple {636#true} assume !(~index > 0); {636#true} is VALID [2018-11-23 12:56:42,366 INFO L273 TraceCheckUtils]: 24: Hoare triple {636#true} call write~int(~data, ~head.base, 8 + ~head.offset, 4); {636#true} is VALID [2018-11-23 12:56:42,367 INFO L273 TraceCheckUtils]: 25: Hoare triple {636#true} assume true; {636#true} is VALID [2018-11-23 12:56:42,367 INFO L268 TraceCheckUtils]: 26: Hoare quadruple {636#true} {637#false} #143#return; {637#false} is VALID [2018-11-23 12:56:42,368 INFO L273 TraceCheckUtils]: 27: Hoare triple {637#false} #t~post14 := ~i~0;~i~0 := #t~post14 - 1;havoc #t~post14; {637#false} is VALID [2018-11-23 12:56:42,368 INFO L273 TraceCheckUtils]: 28: Hoare triple {637#false} assume !(~i~0 > -1); {637#false} is VALID [2018-11-23 12:56:42,369 INFO L273 TraceCheckUtils]: 29: Hoare triple {637#false} ~i~0 := ~len~0 - 1; {637#false} is VALID [2018-11-23 12:56:42,369 INFO L273 TraceCheckUtils]: 30: Hoare triple {637#false} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {637#false} is VALID [2018-11-23 12:56:42,369 INFO L256 TraceCheckUtils]: 31: Hoare triple {637#false} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {636#true} is VALID [2018-11-23 12:56:42,369 INFO L273 TraceCheckUtils]: 32: Hoare triple {636#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {636#true} is VALID [2018-11-23 12:56:42,369 INFO L273 TraceCheckUtils]: 33: Hoare triple {636#true} assume !(~index > 0); {636#true} is VALID [2018-11-23 12:56:42,370 INFO L273 TraceCheckUtils]: 34: Hoare triple {636#true} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {636#true} is VALID [2018-11-23 12:56:42,370 INFO L273 TraceCheckUtils]: 35: Hoare triple {636#true} assume true; {636#true} is VALID [2018-11-23 12:56:42,370 INFO L268 TraceCheckUtils]: 36: Hoare quadruple {636#true} {637#false} #145#return; {637#false} is VALID [2018-11-23 12:56:42,370 INFO L273 TraceCheckUtils]: 37: Hoare triple {637#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {637#false} is VALID [2018-11-23 12:56:42,371 INFO L273 TraceCheckUtils]: 38: Hoare triple {637#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {637#false} is VALID [2018-11-23 12:56:42,371 INFO L273 TraceCheckUtils]: 39: Hoare triple {637#false} assume !false; {637#false} is VALID [2018-11-23 12:56:42,374 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-11-23 12:56:42,375 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-23 12:56:42,375 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-23 12:56:42,376 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 40 [2018-11-23 12:56:42,376 INFO L84 Accepts]: Finished accepts. word is accepted. [2018-11-23 12:56:42,376 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 5 states. [2018-11-23 12:56:42,466 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:42,467 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-23 12:56:42,467 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-23 12:56:42,467 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-11-23 12:56:42,467 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand 5 states. [2018-11-23 12:56:42,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:42,840 INFO L93 Difference]: Finished difference Result 77 states and 89 transitions. [2018-11-23 12:56:42,840 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-23 12:56:42,841 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 40 [2018-11-23 12:56:42,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-23 12:56:42,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-11-23 12:56:42,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 87 transitions. [2018-11-23 12:56:42,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-11-23 12:56:42,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 87 transitions. [2018-11-23 12:56:42,849 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 5 states and 87 transitions. [2018-11-23 12:56:43,005 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 87 edges. 87 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:43,009 INFO L225 Difference]: With dead ends: 77 [2018-11-23 12:56:43,010 INFO L226 Difference]: Without dead ends: 51 [2018-11-23 12:56:43,010 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-11-23 12:56:43,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-11-23 12:56:43,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 47. [2018-11-23 12:56:43,064 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2018-11-23 12:56:43,064 INFO L82 GeneralOperation]: Start isEquivalent. First operand 51 states. Second operand 47 states. [2018-11-23 12:56:43,065 INFO L74 IsIncluded]: Start isIncluded. First operand 51 states. Second operand 47 states. [2018-11-23 12:56:43,065 INFO L87 Difference]: Start difference. First operand 51 states. Second operand 47 states. [2018-11-23 12:56:43,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:43,068 INFO L93 Difference]: Finished difference Result 51 states and 59 transitions. [2018-11-23 12:56:43,068 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-11-23 12:56:43,069 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:43,070 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:43,070 INFO L74 IsIncluded]: Start isIncluded. First operand 47 states. Second operand 51 states. [2018-11-23 12:56:43,070 INFO L87 Difference]: Start difference. First operand 47 states. Second operand 51 states. [2018-11-23 12:56:43,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:43,074 INFO L93 Difference]: Finished difference Result 51 states and 59 transitions. [2018-11-23 12:56:43,074 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-11-23 12:56:43,075 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:43,075 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:43,076 INFO L88 GeneralOperation]: Finished isEquivalent. [2018-11-23 12:56:43,076 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2018-11-23 12:56:43,076 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-11-23 12:56:43,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 53 transitions. [2018-11-23 12:56:43,079 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 53 transitions. Word has length 40 [2018-11-23 12:56:43,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-23 12:56:43,079 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 53 transitions. [2018-11-23 12:56:43,079 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-23 12:56:43,080 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 53 transitions. [2018-11-23 12:56:43,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-11-23 12:56:43,081 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:43,081 INFO L402 BasicCegarLoop]: trace histogram [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] [2018-11-23 12:56:43,082 INFO L423 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:43,082 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:43,082 INFO L82 PathProgramCache]: Analyzing trace with hash 811064934, now seen corresponding path program 1 times [2018-11-23 12:56:43,082 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:43,083 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:43,084 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:43,084 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:43,085 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:43,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:43,392 INFO L256 TraceCheckUtils]: 0: Hoare triple {924#true} call ULTIMATE.init(); {924#true} is VALID [2018-11-23 12:56:43,392 INFO L273 TraceCheckUtils]: 1: Hoare triple {924#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {924#true} is VALID [2018-11-23 12:56:43,393 INFO L273 TraceCheckUtils]: 2: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,393 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {924#true} {924#true} #153#return; {924#true} is VALID [2018-11-23 12:56:43,394 INFO L256 TraceCheckUtils]: 4: Hoare triple {924#true} call #t~ret17 := main(); {924#true} is VALID [2018-11-23 12:56:43,394 INFO L273 TraceCheckUtils]: 5: Hoare triple {924#true} ~len~0 := 2;~data~0 := 1; {926#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:43,395 INFO L256 TraceCheckUtils]: 6: Hoare triple {926#(<= 2 main_~len~0)} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {924#true} is VALID [2018-11-23 12:56:43,395 INFO L273 TraceCheckUtils]: 7: Hoare triple {924#true} ~len := #in~len;~data := #in~data; {924#true} is VALID [2018-11-23 12:56:43,395 INFO L256 TraceCheckUtils]: 8: Hoare triple {924#true} call #t~ret3.base, #t~ret3.offset := node_create(~data); {924#true} is VALID [2018-11-23 12:56:43,395 INFO L273 TraceCheckUtils]: 9: Hoare triple {924#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {924#true} is VALID [2018-11-23 12:56:43,396 INFO L273 TraceCheckUtils]: 10: Hoare triple {924#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {924#true} is VALID [2018-11-23 12:56:43,396 INFO L273 TraceCheckUtils]: 11: Hoare triple {924#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {924#true} is VALID [2018-11-23 12:56:43,396 INFO L273 TraceCheckUtils]: 12: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,397 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {924#true} {924#true} #149#return; {924#true} is VALID [2018-11-23 12:56:43,397 INFO L273 TraceCheckUtils]: 14: Hoare triple {924#true} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {924#true} is VALID [2018-11-23 12:56:43,397 INFO L273 TraceCheckUtils]: 15: Hoare triple {924#true} assume !!(~len > 1); {924#true} is VALID [2018-11-23 12:56:43,397 INFO L256 TraceCheckUtils]: 16: Hoare triple {924#true} call #t~ret4.base, #t~ret4.offset := node_create(~data); {924#true} is VALID [2018-11-23 12:56:43,398 INFO L273 TraceCheckUtils]: 17: Hoare triple {924#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {924#true} is VALID [2018-11-23 12:56:43,398 INFO L273 TraceCheckUtils]: 18: Hoare triple {924#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {924#true} is VALID [2018-11-23 12:56:43,398 INFO L273 TraceCheckUtils]: 19: Hoare triple {924#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {924#true} is VALID [2018-11-23 12:56:43,398 INFO L273 TraceCheckUtils]: 20: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,399 INFO L268 TraceCheckUtils]: 21: Hoare quadruple {924#true} {924#true} #151#return; {924#true} is VALID [2018-11-23 12:56:43,399 INFO L273 TraceCheckUtils]: 22: Hoare triple {924#true} ~new_head~0.base, ~new_head~0.offset := #t~ret4.base, #t~ret4.offset;havoc #t~ret4.base, #t~ret4.offset;call write~$Pointer$(~head~0.base, ~head~0.offset, ~new_head~0.base, ~new_head~0.offset, 4); {924#true} is VALID [2018-11-23 12:56:43,399 INFO L273 TraceCheckUtils]: 23: Hoare triple {924#true} assume ~head~0.base != 0 || ~head~0.offset != 0;call write~$Pointer$(~new_head~0.base, ~new_head~0.offset, ~head~0.base, 4 + ~head~0.offset, 4); {924#true} is VALID [2018-11-23 12:56:43,400 INFO L273 TraceCheckUtils]: 24: Hoare triple {924#true} ~head~0.base, ~head~0.offset := ~new_head~0.base, ~new_head~0.offset;#t~post5 := ~len;~len := #t~post5 - 1;havoc #t~post5; {924#true} is VALID [2018-11-23 12:56:43,400 INFO L273 TraceCheckUtils]: 25: Hoare triple {924#true} assume !(~len > 1); {924#true} is VALID [2018-11-23 12:56:43,400 INFO L273 TraceCheckUtils]: 26: Hoare triple {924#true} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {924#true} is VALID [2018-11-23 12:56:43,401 INFO L273 TraceCheckUtils]: 27: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,414 INFO L268 TraceCheckUtils]: 28: Hoare quadruple {924#true} {926#(<= 2 main_~len~0)} #141#return; {926#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:43,415 INFO L273 TraceCheckUtils]: 29: Hoare triple {926#(<= 2 main_~len~0)} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {927#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:43,419 INFO L273 TraceCheckUtils]: 30: Hoare triple {927#(<= 1 main_~i~0)} assume !!(~i~0 > -1);~new_data~0 := ~i~0 + ~len~0; {927#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:43,419 INFO L256 TraceCheckUtils]: 31: Hoare triple {927#(<= 1 main_~i~0)} call dll_circular_update_at(~s~0.base, ~s~0.offset, ~new_data~0, ~i~0); {924#true} is VALID [2018-11-23 12:56:43,419 INFO L273 TraceCheckUtils]: 32: Hoare triple {924#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~data := #in~data;~index := #in~index; {924#true} is VALID [2018-11-23 12:56:43,419 INFO L273 TraceCheckUtils]: 33: Hoare triple {924#true} assume !(~index > 0); {924#true} is VALID [2018-11-23 12:56:43,420 INFO L273 TraceCheckUtils]: 34: Hoare triple {924#true} call write~int(~data, ~head.base, 8 + ~head.offset, 4); {924#true} is VALID [2018-11-23 12:56:43,420 INFO L273 TraceCheckUtils]: 35: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,421 INFO L268 TraceCheckUtils]: 36: Hoare quadruple {924#true} {927#(<= 1 main_~i~0)} #143#return; {927#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:43,426 INFO L273 TraceCheckUtils]: 37: Hoare triple {927#(<= 1 main_~i~0)} #t~post14 := ~i~0;~i~0 := #t~post14 - 1;havoc #t~post14; {928#(<= 0 main_~i~0)} is VALID [2018-11-23 12:56:43,429 INFO L273 TraceCheckUtils]: 38: Hoare triple {928#(<= 0 main_~i~0)} assume !(~i~0 > -1); {925#false} is VALID [2018-11-23 12:56:43,429 INFO L273 TraceCheckUtils]: 39: Hoare triple {925#false} ~i~0 := ~len~0 - 1; {925#false} is VALID [2018-11-23 12:56:43,429 INFO L273 TraceCheckUtils]: 40: Hoare triple {925#false} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {925#false} is VALID [2018-11-23 12:56:43,430 INFO L256 TraceCheckUtils]: 41: Hoare triple {925#false} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {924#true} is VALID [2018-11-23 12:56:43,430 INFO L273 TraceCheckUtils]: 42: Hoare triple {924#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {924#true} is VALID [2018-11-23 12:56:43,430 INFO L273 TraceCheckUtils]: 43: Hoare triple {924#true} assume !(~index > 0); {924#true} is VALID [2018-11-23 12:56:43,431 INFO L273 TraceCheckUtils]: 44: Hoare triple {924#true} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {924#true} is VALID [2018-11-23 12:56:43,431 INFO L273 TraceCheckUtils]: 45: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:43,431 INFO L268 TraceCheckUtils]: 46: Hoare quadruple {924#true} {925#false} #145#return; {925#false} is VALID [2018-11-23 12:56:43,432 INFO L273 TraceCheckUtils]: 47: Hoare triple {925#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {925#false} is VALID [2018-11-23 12:56:43,432 INFO L273 TraceCheckUtils]: 48: Hoare triple {925#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {925#false} is VALID [2018-11-23 12:56:43,432 INFO L273 TraceCheckUtils]: 49: Hoare triple {925#false} assume !false; {925#false} is VALID [2018-11-23 12:56:43,436 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-11-23 12:56:43,437 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-23 12:56:43,437 INFO L223 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-23 12:56:43,454 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:43,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:43,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:43,569 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-23 12:56:44,118 INFO L256 TraceCheckUtils]: 0: Hoare triple {924#true} call ULTIMATE.init(); {924#true} is VALID [2018-11-23 12:56:44,118 INFO L273 TraceCheckUtils]: 1: Hoare triple {924#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {924#true} is VALID [2018-11-23 12:56:44,118 INFO L273 TraceCheckUtils]: 2: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:44,119 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {924#true} {924#true} #153#return; {924#true} is VALID [2018-11-23 12:56:44,119 INFO L256 TraceCheckUtils]: 4: Hoare triple {924#true} call #t~ret17 := main(); {924#true} is VALID [2018-11-23 12:56:44,119 INFO L273 TraceCheckUtils]: 5: Hoare triple {924#true} ~len~0 := 2;~data~0 := 1; {926#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:44,120 INFO L256 TraceCheckUtils]: 6: Hoare triple {926#(<= 2 main_~len~0)} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {924#true} is VALID [2018-11-23 12:56:44,120 INFO L273 TraceCheckUtils]: 7: Hoare triple {924#true} ~len := #in~len;~data := #in~data; {924#true} is VALID [2018-11-23 12:56:44,120 INFO L256 TraceCheckUtils]: 8: Hoare triple {924#true} call #t~ret3.base, #t~ret3.offset := node_create(~data); {924#true} is VALID [2018-11-23 12:56:44,120 INFO L273 TraceCheckUtils]: 9: Hoare triple {924#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {924#true} is VALID [2018-11-23 12:56:44,120 INFO L273 TraceCheckUtils]: 10: Hoare triple {924#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {924#true} is VALID [2018-11-23 12:56:44,121 INFO L273 TraceCheckUtils]: 11: Hoare triple {924#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {924#true} is VALID [2018-11-23 12:56:44,121 INFO L273 TraceCheckUtils]: 12: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:44,121 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {924#true} {924#true} #149#return; {924#true} is VALID [2018-11-23 12:56:44,121 INFO L273 TraceCheckUtils]: 14: Hoare triple {924#true} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {924#true} is VALID [2018-11-23 12:56:44,122 INFO L273 TraceCheckUtils]: 15: Hoare triple {924#true} assume !!(~len > 1); {924#true} is VALID [2018-11-23 12:56:44,122 INFO L256 TraceCheckUtils]: 16: Hoare triple {924#true} call #t~ret4.base, #t~ret4.offset := node_create(~data); {924#true} is VALID [2018-11-23 12:56:44,122 INFO L273 TraceCheckUtils]: 17: Hoare triple {924#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {924#true} is VALID [2018-11-23 12:56:44,122 INFO L273 TraceCheckUtils]: 18: Hoare triple {924#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {924#true} is VALID [2018-11-23 12:56:44,122 INFO L273 TraceCheckUtils]: 19: Hoare triple {924#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {924#true} is VALID [2018-11-23 12:56:44,123 INFO L273 TraceCheckUtils]: 20: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:44,123 INFO L268 TraceCheckUtils]: 21: Hoare quadruple {924#true} {924#true} #151#return; {924#true} is VALID [2018-11-23 12:56:44,123 INFO L273 TraceCheckUtils]: 22: Hoare triple {924#true} ~new_head~0.base, ~new_head~0.offset := #t~ret4.base, #t~ret4.offset;havoc #t~ret4.base, #t~ret4.offset;call write~$Pointer$(~head~0.base, ~head~0.offset, ~new_head~0.base, ~new_head~0.offset, 4); {924#true} is VALID [2018-11-23 12:56:44,123 INFO L273 TraceCheckUtils]: 23: Hoare triple {924#true} assume ~head~0.base != 0 || ~head~0.offset != 0;call write~$Pointer$(~new_head~0.base, ~new_head~0.offset, ~head~0.base, 4 + ~head~0.offset, 4); {924#true} is VALID [2018-11-23 12:56:44,123 INFO L273 TraceCheckUtils]: 24: Hoare triple {924#true} ~head~0.base, ~head~0.offset := ~new_head~0.base, ~new_head~0.offset;#t~post5 := ~len;~len := #t~post5 - 1;havoc #t~post5; {924#true} is VALID [2018-11-23 12:56:44,124 INFO L273 TraceCheckUtils]: 25: Hoare triple {924#true} assume !(~len > 1); {924#true} is VALID [2018-11-23 12:56:44,124 INFO L273 TraceCheckUtils]: 26: Hoare triple {924#true} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {924#true} is VALID [2018-11-23 12:56:44,124 INFO L273 TraceCheckUtils]: 27: Hoare triple {924#true} assume true; {924#true} is VALID [2018-11-23 12:56:44,125 INFO L268 TraceCheckUtils]: 28: Hoare quadruple {924#true} {926#(<= 2 main_~len~0)} #141#return; {926#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:44,126 INFO L273 TraceCheckUtils]: 29: Hoare triple {926#(<= 2 main_~len~0)} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {927#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:44,128 INFO L273 TraceCheckUtils]: 30: Hoare triple {927#(<= 1 main_~i~0)} assume !!(~i~0 > -1);~new_data~0 := ~i~0 + ~len~0; {927#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:44,128 INFO L256 TraceCheckUtils]: 31: Hoare triple {927#(<= 1 main_~i~0)} call dll_circular_update_at(~s~0.base, ~s~0.offset, ~new_data~0, ~i~0); {924#true} is VALID [2018-11-23 12:56:44,129 INFO L273 TraceCheckUtils]: 32: Hoare triple {924#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~data := #in~data;~index := #in~index; {1028#(<= |dll_circular_update_at_#in~index| dll_circular_update_at_~index)} is VALID [2018-11-23 12:56:44,130 INFO L273 TraceCheckUtils]: 33: Hoare triple {1028#(<= |dll_circular_update_at_#in~index| dll_circular_update_at_~index)} assume !(~index > 0); {1032#(<= |dll_circular_update_at_#in~index| 0)} is VALID [2018-11-23 12:56:44,132 INFO L273 TraceCheckUtils]: 34: Hoare triple {1032#(<= |dll_circular_update_at_#in~index| 0)} call write~int(~data, ~head.base, 8 + ~head.offset, 4); {1032#(<= |dll_circular_update_at_#in~index| 0)} is VALID [2018-11-23 12:56:44,134 INFO L273 TraceCheckUtils]: 35: Hoare triple {1032#(<= |dll_circular_update_at_#in~index| 0)} assume true; {1032#(<= |dll_circular_update_at_#in~index| 0)} is VALID [2018-11-23 12:56:44,135 INFO L268 TraceCheckUtils]: 36: Hoare quadruple {1032#(<= |dll_circular_update_at_#in~index| 0)} {927#(<= 1 main_~i~0)} #143#return; {925#false} is VALID [2018-11-23 12:56:44,135 INFO L273 TraceCheckUtils]: 37: Hoare triple {925#false} #t~post14 := ~i~0;~i~0 := #t~post14 - 1;havoc #t~post14; {925#false} is VALID [2018-11-23 12:56:44,136 INFO L273 TraceCheckUtils]: 38: Hoare triple {925#false} assume !(~i~0 > -1); {925#false} is VALID [2018-11-23 12:56:44,136 INFO L273 TraceCheckUtils]: 39: Hoare triple {925#false} ~i~0 := ~len~0 - 1; {925#false} is VALID [2018-11-23 12:56:44,136 INFO L273 TraceCheckUtils]: 40: Hoare triple {925#false} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {925#false} is VALID [2018-11-23 12:56:44,136 INFO L256 TraceCheckUtils]: 41: Hoare triple {925#false} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {925#false} is VALID [2018-11-23 12:56:44,137 INFO L273 TraceCheckUtils]: 42: Hoare triple {925#false} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {925#false} is VALID [2018-11-23 12:56:44,137 INFO L273 TraceCheckUtils]: 43: Hoare triple {925#false} assume !(~index > 0); {925#false} is VALID [2018-11-23 12:56:44,137 INFO L273 TraceCheckUtils]: 44: Hoare triple {925#false} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {925#false} is VALID [2018-11-23 12:56:44,138 INFO L273 TraceCheckUtils]: 45: Hoare triple {925#false} assume true; {925#false} is VALID [2018-11-23 12:56:44,138 INFO L268 TraceCheckUtils]: 46: Hoare quadruple {925#false} {925#false} #145#return; {925#false} is VALID [2018-11-23 12:56:44,138 INFO L273 TraceCheckUtils]: 47: Hoare triple {925#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {925#false} is VALID [2018-11-23 12:56:44,139 INFO L273 TraceCheckUtils]: 48: Hoare triple {925#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {925#false} is VALID [2018-11-23 12:56:44,139 INFO L273 TraceCheckUtils]: 49: Hoare triple {925#false} assume !false; {925#false} is VALID [2018-11-23 12:56:44,143 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-11-23 12:56:44,173 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-11-23 12:56:44,173 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [5] total 7 [2018-11-23 12:56:44,174 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 50 [2018-11-23 12:56:44,175 INFO L84 Accepts]: Finished accepts. word is accepted. [2018-11-23 12:56:44,175 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 7 states. [2018-11-23 12:56:44,341 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 59 edges. 59 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:44,341 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-11-23 12:56:44,341 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-11-23 12:56:44,341 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-11-23 12:56:44,342 INFO L87 Difference]: Start difference. First operand 47 states and 53 transitions. Second operand 7 states. [2018-11-23 12:56:45,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:45,078 INFO L93 Difference]: Finished difference Result 83 states and 97 transitions. [2018-11-23 12:56:45,078 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-11-23 12:56:45,079 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 50 [2018-11-23 12:56:45,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-23 12:56:45,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-11-23 12:56:45,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 96 transitions. [2018-11-23 12:56:45,083 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-11-23 12:56:45,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 96 transitions. [2018-11-23 12:56:45,086 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 7 states and 96 transitions. [2018-11-23 12:56:45,241 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 96 edges. 96 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:45,245 INFO L225 Difference]: With dead ends: 83 [2018-11-23 12:56:45,246 INFO L226 Difference]: Without dead ends: 62 [2018-11-23 12:56:45,246 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-11-23 12:56:45,248 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2018-11-23 12:56:45,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 54. [2018-11-23 12:56:45,301 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2018-11-23 12:56:45,301 INFO L82 GeneralOperation]: Start isEquivalent. First operand 62 states. Second operand 54 states. [2018-11-23 12:56:45,302 INFO L74 IsIncluded]: Start isIncluded. First operand 62 states. Second operand 54 states. [2018-11-23 12:56:45,302 INFO L87 Difference]: Start difference. First operand 62 states. Second operand 54 states. [2018-11-23 12:56:45,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:45,305 INFO L93 Difference]: Finished difference Result 62 states and 71 transitions. [2018-11-23 12:56:45,305 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2018-11-23 12:56:45,306 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:45,306 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:45,307 INFO L74 IsIncluded]: Start isIncluded. First operand 54 states. Second operand 62 states. [2018-11-23 12:56:45,307 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 62 states. [2018-11-23 12:56:45,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:45,311 INFO L93 Difference]: Finished difference Result 62 states and 71 transitions. [2018-11-23 12:56:45,311 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2018-11-23 12:56:45,312 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:45,312 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:45,312 INFO L88 GeneralOperation]: Finished isEquivalent. [2018-11-23 12:56:45,312 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2018-11-23 12:56:45,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-11-23 12:56:45,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 62 transitions. [2018-11-23 12:56:45,316 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 62 transitions. Word has length 50 [2018-11-23 12:56:45,316 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-23 12:56:45,316 INFO L480 AbstractCegarLoop]: Abstraction has 54 states and 62 transitions. [2018-11-23 12:56:45,316 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-11-23 12:56:45,317 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 62 transitions. [2018-11-23 12:56:45,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-11-23 12:56:45,318 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:45,318 INFO L402 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-23 12:56:45,319 INFO L423 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:45,319 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:45,319 INFO L82 PathProgramCache]: Analyzing trace with hash -1753006870, now seen corresponding path program 1 times [2018-11-23 12:56:45,319 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:45,319 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:45,321 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:45,321 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:45,321 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:45,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:45,520 INFO L256 TraceCheckUtils]: 0: Hoare triple {1408#true} call ULTIMATE.init(); {1408#true} is VALID [2018-11-23 12:56:45,520 INFO L273 TraceCheckUtils]: 1: Hoare triple {1408#true} #NULL.base, #NULL.offset := 0, 0;#valid := #valid[0 := 0]; {1408#true} is VALID [2018-11-23 12:56:45,521 INFO L273 TraceCheckUtils]: 2: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,521 INFO L268 TraceCheckUtils]: 3: Hoare quadruple {1408#true} {1408#true} #153#return; {1408#true} is VALID [2018-11-23 12:56:45,522 INFO L256 TraceCheckUtils]: 4: Hoare triple {1408#true} call #t~ret17 := main(); {1408#true} is VALID [2018-11-23 12:56:45,522 INFO L273 TraceCheckUtils]: 5: Hoare triple {1408#true} ~len~0 := 2;~data~0 := 1; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,522 INFO L256 TraceCheckUtils]: 6: Hoare triple {1410#(<= 2 main_~len~0)} call #t~ret13.base, #t~ret13.offset := dll_circular_create(~len~0, ~data~0); {1408#true} is VALID [2018-11-23 12:56:45,523 INFO L273 TraceCheckUtils]: 7: Hoare triple {1408#true} ~len := #in~len;~data := #in~data; {1408#true} is VALID [2018-11-23 12:56:45,523 INFO L256 TraceCheckUtils]: 8: Hoare triple {1408#true} call #t~ret3.base, #t~ret3.offset := node_create(~data); {1408#true} is VALID [2018-11-23 12:56:45,523 INFO L273 TraceCheckUtils]: 9: Hoare triple {1408#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {1408#true} is VALID [2018-11-23 12:56:45,523 INFO L273 TraceCheckUtils]: 10: Hoare triple {1408#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {1408#true} is VALID [2018-11-23 12:56:45,523 INFO L273 TraceCheckUtils]: 11: Hoare triple {1408#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {1408#true} is VALID [2018-11-23 12:56:45,524 INFO L273 TraceCheckUtils]: 12: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,524 INFO L268 TraceCheckUtils]: 13: Hoare quadruple {1408#true} {1408#true} #149#return; {1408#true} is VALID [2018-11-23 12:56:45,524 INFO L273 TraceCheckUtils]: 14: Hoare triple {1408#true} ~head~0.base, ~head~0.offset := #t~ret3.base, #t~ret3.offset;havoc #t~ret3.base, #t~ret3.offset;~last~0.base, ~last~0.offset := ~head~0.base, ~head~0.offset; {1408#true} is VALID [2018-11-23 12:56:45,525 INFO L273 TraceCheckUtils]: 15: Hoare triple {1408#true} assume !!(~len > 1); {1408#true} is VALID [2018-11-23 12:56:45,525 INFO L256 TraceCheckUtils]: 16: Hoare triple {1408#true} call #t~ret4.base, #t~ret4.offset := node_create(~data); {1408#true} is VALID [2018-11-23 12:56:45,525 INFO L273 TraceCheckUtils]: 17: Hoare triple {1408#true} ~data := #in~data;call #t~malloc2.base, #t~malloc2.offset := #Ultimate.alloc(12);~temp~0.base, ~temp~0.offset := #t~malloc2.base, #t~malloc2.offset; {1408#true} is VALID [2018-11-23 12:56:45,525 INFO L273 TraceCheckUtils]: 18: Hoare triple {1408#true} assume !(0 == ~temp~0.base && 0 == ~temp~0.offset); {1408#true} is VALID [2018-11-23 12:56:45,526 INFO L273 TraceCheckUtils]: 19: Hoare triple {1408#true} call write~$Pointer$(0, 0, ~temp~0.base, ~temp~0.offset, 4);call write~$Pointer$(0, 0, ~temp~0.base, 4 + ~temp~0.offset, 4);call write~int(~data, ~temp~0.base, 8 + ~temp~0.offset, 4);#res.base, #res.offset := ~temp~0.base, ~temp~0.offset; {1408#true} is VALID [2018-11-23 12:56:45,526 INFO L273 TraceCheckUtils]: 20: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,526 INFO L268 TraceCheckUtils]: 21: Hoare quadruple {1408#true} {1408#true} #151#return; {1408#true} is VALID [2018-11-23 12:56:45,526 INFO L273 TraceCheckUtils]: 22: Hoare triple {1408#true} ~new_head~0.base, ~new_head~0.offset := #t~ret4.base, #t~ret4.offset;havoc #t~ret4.base, #t~ret4.offset;call write~$Pointer$(~head~0.base, ~head~0.offset, ~new_head~0.base, ~new_head~0.offset, 4); {1408#true} is VALID [2018-11-23 12:56:45,527 INFO L273 TraceCheckUtils]: 23: Hoare triple {1408#true} assume ~head~0.base != 0 || ~head~0.offset != 0;call write~$Pointer$(~new_head~0.base, ~new_head~0.offset, ~head~0.base, 4 + ~head~0.offset, 4); {1408#true} is VALID [2018-11-23 12:56:45,527 INFO L273 TraceCheckUtils]: 24: Hoare triple {1408#true} ~head~0.base, ~head~0.offset := ~new_head~0.base, ~new_head~0.offset;#t~post5 := ~len;~len := #t~post5 - 1;havoc #t~post5; {1408#true} is VALID [2018-11-23 12:56:45,527 INFO L273 TraceCheckUtils]: 25: Hoare triple {1408#true} assume !(~len > 1); {1408#true} is VALID [2018-11-23 12:56:45,527 INFO L273 TraceCheckUtils]: 26: Hoare triple {1408#true} call write~$Pointer$(~head~0.base, ~head~0.offset, ~last~0.base, ~last~0.offset, 4);call write~$Pointer$(~last~0.base, ~last~0.offset, ~head~0.base, 4 + ~head~0.offset, 4);#res.base, #res.offset := ~head~0.base, ~head~0.offset; {1408#true} is VALID [2018-11-23 12:56:45,528 INFO L273 TraceCheckUtils]: 27: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,537 INFO L268 TraceCheckUtils]: 28: Hoare quadruple {1408#true} {1410#(<= 2 main_~len~0)} #141#return; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,537 INFO L273 TraceCheckUtils]: 29: Hoare triple {1410#(<= 2 main_~len~0)} ~s~0.base, ~s~0.offset := #t~ret13.base, #t~ret13.offset;havoc #t~ret13.base, #t~ret13.offset;~i~0 := 0;~i~0 := ~len~0 - 1; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,539 INFO L273 TraceCheckUtils]: 30: Hoare triple {1410#(<= 2 main_~len~0)} assume !!(~i~0 > -1);~new_data~0 := ~i~0 + ~len~0; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,539 INFO L256 TraceCheckUtils]: 31: Hoare triple {1410#(<= 2 main_~len~0)} call dll_circular_update_at(~s~0.base, ~s~0.offset, ~new_data~0, ~i~0); {1408#true} is VALID [2018-11-23 12:56:45,539 INFO L273 TraceCheckUtils]: 32: Hoare triple {1408#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~data := #in~data;~index := #in~index; {1408#true} is VALID [2018-11-23 12:56:45,540 INFO L273 TraceCheckUtils]: 33: Hoare triple {1408#true} assume !!(~index > 0);call #t~mem11.base, #t~mem11.offset := read~$Pointer$(~head.base, ~head.offset, 4);~head.base, ~head.offset := #t~mem11.base, #t~mem11.offset;havoc #t~mem11.base, #t~mem11.offset;#t~post12 := ~index;~index := #t~post12 - 1;havoc #t~post12; {1408#true} is VALID [2018-11-23 12:56:45,541 INFO L273 TraceCheckUtils]: 34: Hoare triple {1408#true} assume !(~index > 0); {1408#true} is VALID [2018-11-23 12:56:45,541 INFO L273 TraceCheckUtils]: 35: Hoare triple {1408#true} call write~int(~data, ~head.base, 8 + ~head.offset, 4); {1408#true} is VALID [2018-11-23 12:56:45,541 INFO L273 TraceCheckUtils]: 36: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,543 INFO L268 TraceCheckUtils]: 37: Hoare quadruple {1408#true} {1410#(<= 2 main_~len~0)} #143#return; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,543 INFO L273 TraceCheckUtils]: 38: Hoare triple {1410#(<= 2 main_~len~0)} #t~post14 := ~i~0;~i~0 := #t~post14 - 1;havoc #t~post14; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,545 INFO L273 TraceCheckUtils]: 39: Hoare triple {1410#(<= 2 main_~len~0)} assume !!(~i~0 > -1);~new_data~0 := ~i~0 + ~len~0; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,545 INFO L256 TraceCheckUtils]: 40: Hoare triple {1410#(<= 2 main_~len~0)} call dll_circular_update_at(~s~0.base, ~s~0.offset, ~new_data~0, ~i~0); {1408#true} is VALID [2018-11-23 12:56:45,545 INFO L273 TraceCheckUtils]: 41: Hoare triple {1408#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~data := #in~data;~index := #in~index; {1408#true} is VALID [2018-11-23 12:56:45,545 INFO L273 TraceCheckUtils]: 42: Hoare triple {1408#true} assume !(~index > 0); {1408#true} is VALID [2018-11-23 12:56:45,546 INFO L273 TraceCheckUtils]: 43: Hoare triple {1408#true} call write~int(~data, ~head.base, 8 + ~head.offset, 4); {1408#true} is VALID [2018-11-23 12:56:45,546 INFO L273 TraceCheckUtils]: 44: Hoare triple {1408#true} assume true; {1408#true} is VALID [2018-11-23 12:56:45,555 INFO L268 TraceCheckUtils]: 45: Hoare quadruple {1408#true} {1410#(<= 2 main_~len~0)} #143#return; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,556 INFO L273 TraceCheckUtils]: 46: Hoare triple {1410#(<= 2 main_~len~0)} #t~post14 := ~i~0;~i~0 := #t~post14 - 1;havoc #t~post14; {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,560 INFO L273 TraceCheckUtils]: 47: Hoare triple {1410#(<= 2 main_~len~0)} assume !(~i~0 > -1); {1410#(<= 2 main_~len~0)} is VALID [2018-11-23 12:56:45,562 INFO L273 TraceCheckUtils]: 48: Hoare triple {1410#(<= 2 main_~len~0)} ~i~0 := ~len~0 - 1; {1411#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:45,564 INFO L273 TraceCheckUtils]: 49: Hoare triple {1411#(<= 1 main_~i~0)} assume !!(~i~0 > -1);~expected~0 := ~i~0 + ~len~0; {1411#(<= 1 main_~i~0)} is VALID [2018-11-23 12:56:45,564 INFO L256 TraceCheckUtils]: 50: Hoare triple {1411#(<= 1 main_~i~0)} call #t~ret16 := dll_circular_get_data_at(~s~0.base, ~s~0.offset, ~i~0); {1408#true} is VALID [2018-11-23 12:56:45,566 INFO L273 TraceCheckUtils]: 51: Hoare triple {1408#true} ~head.base, ~head.offset := #in~head.base, #in~head.offset;~index := #in~index; {1412#(<= |dll_circular_get_data_at_#in~index| dll_circular_get_data_at_~index)} is VALID [2018-11-23 12:56:45,572 INFO L273 TraceCheckUtils]: 52: Hoare triple {1412#(<= |dll_circular_get_data_at_#in~index| dll_circular_get_data_at_~index)} assume !(~index > 0); {1413#(<= |dll_circular_get_data_at_#in~index| 0)} is VALID [2018-11-23 12:56:45,574 INFO L273 TraceCheckUtils]: 53: Hoare triple {1413#(<= |dll_circular_get_data_at_#in~index| 0)} call #t~mem10 := read~int(~head.base, 8 + ~head.offset, 4);#res := #t~mem10;havoc #t~mem10; {1413#(<= |dll_circular_get_data_at_#in~index| 0)} is VALID [2018-11-23 12:56:45,574 INFO L273 TraceCheckUtils]: 54: Hoare triple {1413#(<= |dll_circular_get_data_at_#in~index| 0)} assume true; {1413#(<= |dll_circular_get_data_at_#in~index| 0)} is VALID [2018-11-23 12:56:45,580 INFO L268 TraceCheckUtils]: 55: Hoare quadruple {1413#(<= |dll_circular_get_data_at_#in~index| 0)} {1411#(<= 1 main_~i~0)} #145#return; {1409#false} is VALID [2018-11-23 12:56:45,580 INFO L273 TraceCheckUtils]: 56: Hoare triple {1409#false} assume -2147483648 <= #t~ret16 && #t~ret16 <= 2147483647; {1409#false} is VALID [2018-11-23 12:56:45,580 INFO L273 TraceCheckUtils]: 57: Hoare triple {1409#false} assume ~expected~0 != #t~ret16;havoc #t~ret16; {1409#false} is VALID [2018-11-23 12:56:45,581 INFO L273 TraceCheckUtils]: 58: Hoare triple {1409#false} assume !false; {1409#false} is VALID [2018-11-23 12:56:45,585 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-11-23 12:56:45,586 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-23 12:56:45,586 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-11-23 12:56:45,587 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 59 [2018-11-23 12:56:45,587 INFO L84 Accepts]: Finished accepts. word is accepted. [2018-11-23 12:56:45,587 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 6 states. [2018-11-23 12:56:45,695 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 47 edges. 47 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:45,695 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-11-23 12:56:45,696 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-11-23 12:56:45,696 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-11-23 12:56:45,696 INFO L87 Difference]: Start difference. First operand 54 states and 62 transitions. Second operand 6 states. [2018-11-23 12:56:46,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:46,212 INFO L93 Difference]: Finished difference Result 77 states and 89 transitions. [2018-11-23 12:56:46,213 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-11-23 12:56:46,213 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 59 [2018-11-23 12:56:46,213 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-23 12:56:46,213 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-11-23 12:56:46,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 82 transitions. [2018-11-23 12:56:46,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-11-23 12:56:46,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 82 transitions. [2018-11-23 12:56:46,219 INFO L86 InductivityCheck]: Starting indutivity check of a Floyd-Hoare automaton with 6 states and 82 transitions. [2018-11-23 12:56:46,346 INFO L119 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2018-11-23 12:56:46,351 INFO L225 Difference]: With dead ends: 77 [2018-11-23 12:56:46,351 INFO L226 Difference]: Without dead ends: 65 [2018-11-23 12:56:46,352 INFO L631 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-11-23 12:56:46,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-11-23 12:56:46,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2018-11-23 12:56:46,504 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2018-11-23 12:56:46,504 INFO L82 GeneralOperation]: Start isEquivalent. First operand 65 states. Second operand 60 states. [2018-11-23 12:56:46,504 INFO L74 IsIncluded]: Start isIncluded. First operand 65 states. Second operand 60 states. [2018-11-23 12:56:46,504 INFO L87 Difference]: Start difference. First operand 65 states. Second operand 60 states. [2018-11-23 12:56:46,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:46,509 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2018-11-23 12:56:46,509 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 75 transitions. [2018-11-23 12:56:46,509 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:46,509 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:46,509 INFO L74 IsIncluded]: Start isIncluded. First operand 60 states. Second operand 65 states. [2018-11-23 12:56:46,510 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 65 states. [2018-11-23 12:56:46,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-23 12:56:46,513 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2018-11-23 12:56:46,513 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 75 transitions. [2018-11-23 12:56:46,514 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-11-23 12:56:46,514 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2018-11-23 12:56:46,514 INFO L88 GeneralOperation]: Finished isEquivalent. [2018-11-23 12:56:46,514 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2018-11-23 12:56:46,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-11-23 12:56:46,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 70 transitions. [2018-11-23 12:56:46,518 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 70 transitions. Word has length 59 [2018-11-23 12:56:46,518 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-23 12:56:46,518 INFO L480 AbstractCegarLoop]: Abstraction has 60 states and 70 transitions. [2018-11-23 12:56:46,518 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-11-23 12:56:46,518 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 70 transitions. [2018-11-23 12:56:46,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-11-23 12:56:46,520 INFO L394 BasicCegarLoop]: Found error trace [2018-11-23 12:56:46,520 INFO L402 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-23 12:56:46,520 INFO L423 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-23 12:56:46,520 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-23 12:56:46,521 INFO L82 PathProgramCache]: Analyzing trace with hash -416561991, now seen corresponding path program 1 times [2018-11-23 12:56:46,521 INFO L223 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-11-23 12:56:46,521 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-11-23 12:56:46,522 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:46,522 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-23 12:56:46,522 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-23 12:56:46,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-23 12:56:48,625 FATAL L292 ToolchainWalker]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: zero is neutral element of plus operator at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.UltimateNormalFormUtils.rootRespectsUltimateNormalForm(UltimateNormalFormUtils.java:87) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.UltimateNormalFormUtils.rootRespectsUltimateNormalForm(UltimateNormalFormUtils.java:131) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.UltimateNormalFormUtils.lambda$0(UltimateNormalFormUtils.java:154) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.SubtermPropertyChecker$MyWalker.walk(SubtermPropertyChecker.java:63) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:122) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:113) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.SubtermPropertyChecker.isPropertySatisfied(SubtermPropertyChecker.java:121) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.UltimateNormalFormUtils.respectsUltimateNormalForm(UltimateNormalFormUtils.java:155) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.predicates.BasicPredicateFactory.newPredicate(BasicPredicateFactory.java:103) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.predicates.PredicateUnifier.constructNewPredicate(PredicateUnifier.java:375) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate(PredicateUnifier.java:361) at de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate(PredicateUnifier.java:299) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.singletracecheck.NestedInterpolantsBuilder.computePredicates(NestedInterpolantsBuilder.java:592) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.singletracecheck.NestedInterpolantsBuilder.(NestedInterpolantsBuilder.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolantsTree(InterpolatingTraceCheckCraig.java:271) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolants(InterpolatingTraceCheckCraig.java:207) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.singletracecheck.InterpolatingTraceCheckCraig.(InterpolatingTraceCheckCraig.java:109) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceCheckConstructor.constructCraig(TraceCheckConstructor.java:211) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceCheckConstructor.constructTraceCheck(TraceCheckConstructor.java:183) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceCheckConstructor.get(TraceCheckConstructor.java:165) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.MultiTrackRefinementStrategy.getTraceCheck(MultiTrackRefinementStrategy.java:232) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.BaseRefinementStrategy.checkFeasibility(BaseRefinementStrategy.java:223) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.BaseRefinementStrategy.executeStrategy(BaseRefinementStrategy.java:197) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:70) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:456) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterateInternal(AbstractCegarLoop.java:434) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:376) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.iterate(TraceAbstractionStarter.java:334) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:126) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:316) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55) [2018-11-23 12:56:48,630 INFO L168 Benchmark]: Toolchain (without parser) took 11414.96 ms. Allocated memory was 1.5 GB in the beginning and 2.4 GB in the end (delta: 867.2 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -808.0 MB). Peak memory consumption was 59.2 MB. Max. memory is 7.1 GB. [2018-11-23 12:56:48,632 INFO L168 Benchmark]: CDTParser took 0.18 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-23 12:56:48,632 INFO L168 Benchmark]: CACSL2BoogieTranslator took 779.13 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 728.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -787.7 MB). Peak memory consumption was 41.5 MB. Max. memory is 7.1 GB. [2018-11-23 12:56:48,633 INFO L168 Benchmark]: Boogie Procedure Inliner took 46.01 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.4 MB). Peak memory consumption was 13.4 MB. Max. memory is 7.1 GB. [2018-11-23 12:56:48,634 INFO L168 Benchmark]: Boogie Preprocessor took 71.37 ms. Allocated memory is still 2.3 GB. Free memory is still 2.2 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-23 12:56:48,634 INFO L168 Benchmark]: RCFGBuilder took 1157.54 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.1 GB in the end (delta: 50.8 MB). Peak memory consumption was 50.8 MB. Max. memory is 7.1 GB. [2018-11-23 12:56:48,635 INFO L168 Benchmark]: TraceAbstraction took 9353.57 ms. Allocated memory was 2.3 GB in the beginning and 2.4 GB in the end (delta: 138.4 MB). Free memory was 2.1 GB in the beginning and 2.2 GB in the end (delta: -84.4 MB). Peak memory consumption was 54.0 MB. Max. memory is 7.1 GB. [2018-11-23 12:56:48,640 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - GenericResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 779.13 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 728.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -787.7 MB). Peak memory consumption was 41.5 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 46.01 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.2 GB in the end (delta: 13.4 MB). Peak memory consumption was 13.4 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 71.37 ms. Allocated memory is still 2.3 GB. Free memory is still 2.2 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 1157.54 ms. Allocated memory is still 2.3 GB. Free memory was 2.2 GB in the beginning and 2.1 GB in the end (delta: 50.8 MB). Peak memory consumption was 50.8 MB. Max. memory is 7.1 GB. * TraceAbstraction took 9353.57 ms. Allocated memory was 2.3 GB in the beginning and 2.4 GB in the end (delta: 138.4 MB). Free memory was 2.1 GB in the beginning and 2.2 GB in the end (delta: -84.4 MB). Peak memory consumption was 54.0 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: zero is neutral element of plus operator de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: zero is neutral element of plus operator: de.uni_freiburg.informatik.ultimate.modelcheckerutils.smt.UltimateNormalFormUtils.rootRespectsUltimateNormalForm(UltimateNormalFormUtils.java:87) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request...