./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive/Ackermann01-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 839c364b Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/Ackermann01-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 93bcf8b6df587e0bc8cb137c6415932ffc9083999b1b09826c5b148989ca1a7b --- Real Ultimate output --- This is Ultimate 0.2.2-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 14:47:30,177 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 14:47:30,184 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 14:47:30,222 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 14:47:30,223 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 14:47:30,224 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 14:47:30,225 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 14:47:30,226 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 14:47:30,227 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 14:47:30,228 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 14:47:30,229 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 14:47:30,230 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 14:47:30,230 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 14:47:30,231 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 14:47:30,232 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 14:47:30,234 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 14:47:30,234 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 14:47:30,235 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 14:47:30,237 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 14:47:30,238 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 14:47:30,240 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 14:47:30,241 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 14:47:30,242 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 14:47:30,242 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 14:47:30,245 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 14:47:30,245 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 14:47:30,245 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 14:47:30,246 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 14:47:30,246 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 14:47:30,247 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 14:47:30,248 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 14:47:30,248 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 14:47:30,249 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 14:47:30,250 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 14:47:30,250 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 14:47:30,251 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 14:47:30,251 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 14:47:30,252 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 14:47:30,252 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 14:47:30,253 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 14:47:30,253 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 14:47:30,254 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2021-12-14 14:47:30,271 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 14:47:30,271 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 14:47:30,272 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 14:47:30,272 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 14:47:30,273 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-14 14:47:30,273 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-14 14:47:30,273 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 14:47:30,274 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 14:47:30,274 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 14:47:30,274 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 14:47:30,275 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-14 14:47:30,275 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 14:47:30,275 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-14 14:47:30,276 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-14 14:47:30,277 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 14:47:30,278 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-14 14:47:30,278 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 14:47:30,278 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 14:47:30,278 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-14 14:47:30,278 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 14:47:30,279 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 14:47:30,279 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-14 14:47:30,280 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-14 14:47:30,280 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 14:47:30,281 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 93bcf8b6df587e0bc8cb137c6415932ffc9083999b1b09826c5b148989ca1a7b [2021-12-14 14:47:30,497 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 14:47:30,516 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 14:47:30,518 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 14:47:30,519 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 14:47:30,519 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 14:47:30,520 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Ackermann01-2.c [2021-12-14 14:47:30,584 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/989c26c0f/fd8db70c0d214e569a7bf1f112bd89f4/FLAGa24660c68 [2021-12-14 14:47:30,911 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 14:47:30,912 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Ackermann01-2.c [2021-12-14 14:47:30,916 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/989c26c0f/fd8db70c0d214e569a7bf1f112bd89f4/FLAGa24660c68 [2021-12-14 14:47:30,925 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/989c26c0f/fd8db70c0d214e569a7bf1f112bd89f4 [2021-12-14 14:47:30,927 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 14:47:30,929 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 14:47:30,930 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 14:47:30,930 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 14:47:30,937 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 14:47:30,937 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 02:47:30" (1/1) ... [2021-12-14 14:47:30,938 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@66425391 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:30, skipping insertion in model container [2021-12-14 14:47:30,938 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 02:47:30" (1/1) ... [2021-12-14 14:47:30,944 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 14:47:30,957 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 14:47:31,104 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Ackermann01-2.c[1234,1247] [2021-12-14 14:47:31,110 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 14:47:31,119 INFO L203 MainTranslator]: Completed pre-run [2021-12-14 14:47:31,137 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Ackermann01-2.c[1234,1247] [2021-12-14 14:47:31,138 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 14:47:31,150 INFO L208 MainTranslator]: Completed translation [2021-12-14 14:47:31,151 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31 WrapperNode [2021-12-14 14:47:31,151 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 14:47:31,152 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-14 14:47:31,152 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-14 14:47:31,152 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-14 14:47:31,157 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,163 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,174 INFO L137 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 32 [2021-12-14 14:47:31,175 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-14 14:47:31,176 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-14 14:47:31,176 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-14 14:47:31,176 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-14 14:47:31,181 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,182 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,183 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,183 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,185 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,187 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,188 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,189 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-14 14:47:31,190 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-14 14:47:31,190 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-14 14:47:31,190 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-14 14:47:31,198 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (1/1) ... [2021-12-14 14:47:31,205 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-14 14:47:31,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:31,226 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-12-14 14:47:31,235 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-12-14 14:47:31,255 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-14 14:47:31,255 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-14 14:47:31,255 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-14 14:47:31,255 INFO L130 BoogieDeclarations]: Found specification of procedure ackermann [2021-12-14 14:47:31,255 INFO L138 BoogieDeclarations]: Found implementation of procedure ackermann [2021-12-14 14:47:31,256 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-14 14:47:31,302 INFO L236 CfgBuilder]: Building ICFG [2021-12-14 14:47:31,303 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-14 14:47:31,445 INFO L277 CfgBuilder]: Performing block encoding [2021-12-14 14:47:31,452 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-14 14:47:31,454 INFO L301 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-14 14:47:31,456 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 02:47:31 BoogieIcfgContainer [2021-12-14 14:47:31,456 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-14 14:47:31,458 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-14 14:47:31,458 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-14 14:47:31,460 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-14 14:47:31,461 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.12 02:47:30" (1/3) ... [2021-12-14 14:47:31,462 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41fcb19 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 02:47:31, skipping insertion in model container [2021-12-14 14:47:31,462 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 02:47:31" (2/3) ... [2021-12-14 14:47:31,462 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41fcb19 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.12 02:47:31, skipping insertion in model container [2021-12-14 14:47:31,463 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 02:47:31" (3/3) ... [2021-12-14 14:47:31,464 INFO L111 eAbstractionObserver]: Analyzing ICFG Ackermann01-2.c [2021-12-14 14:47:31,468 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-14 14:47:31,468 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-14 14:47:31,518 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-14 14:47:31,528 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2021-12-14 14:47:31,528 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-14 14:47:31,542 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-14 14:47:31,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-12-14 14:47:31,553 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:31,553 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:31,554 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:31,558 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:31,558 INFO L85 PathProgramCache]: Analyzing trace with hash 1470704041, now seen corresponding path program 1 times [2021-12-14 14:47:31,564 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:31,564 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2072168205] [2021-12-14 14:47:31,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:31,565 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:31,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:31,785 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:31,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:31,846 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-14 14:47:31,847 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:31,847 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2072168205] [2021-12-14 14:47:31,848 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2072168205] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:47:31,848 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:47:31,848 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-14 14:47:31,850 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [764144415] [2021-12-14 14:47:31,850 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:47:31,853 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-14 14:47:31,853 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:31,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-14 14:47:31,887 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-14 14:47:31,889 INFO L87 Difference]: Start difference. First operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 7 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 14:47:32,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:32,045 INFO L93 Difference]: Finished difference Result 38 states and 46 transitions. [2021-12-14 14:47:32,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-14 14:47:32,048 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2021-12-14 14:47:32,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:32,058 INFO L225 Difference]: With dead ends: 38 [2021-12-14 14:47:32,059 INFO L226 Difference]: Without dead ends: 22 [2021-12-14 14:47:32,061 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2021-12-14 14:47:32,066 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 21 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 75 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:32,067 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 91 Invalid, 75 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:32,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2021-12-14 14:47:32,108 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2021-12-14 14:47:32,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 22 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-14 14:47:32,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2021-12-14 14:47:32,112 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 12 [2021-12-14 14:47:32,113 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:32,113 INFO L470 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2021-12-14 14:47:32,114 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-14 14:47:32,114 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2021-12-14 14:47:32,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2021-12-14 14:47:32,116 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:32,116 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:32,117 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-14 14:47:32,118 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:32,120 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:32,121 INFO L85 PathProgramCache]: Analyzing trace with hash 941922339, now seen corresponding path program 1 times [2021-12-14 14:47:32,121 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:32,121 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [351849472] [2021-12-14 14:47:32,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:32,122 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:32,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,191 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:32,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,236 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:32,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,275 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-14 14:47:32,276 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:32,276 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [351849472] [2021-12-14 14:47:32,276 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [351849472] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 14:47:32,277 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 14:47:32,277 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2021-12-14 14:47:32,277 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [231168775] [2021-12-14 14:47:32,277 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:47:32,278 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-14 14:47:32,278 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:32,279 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-14 14:47:32,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2021-12-14 14:47:32,279 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand has 8 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:47:32,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:32,375 INFO L93 Difference]: Finished difference Result 29 states and 37 transitions. [2021-12-14 14:47:32,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 14:47:32,376 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 19 [2021-12-14 14:47:32,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:32,377 INFO L225 Difference]: With dead ends: 29 [2021-12-14 14:47:32,377 INFO L226 Difference]: Without dead ends: 25 [2021-12-14 14:47:32,378 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2021-12-14 14:47:32,379 INFO L933 BasicCegarLoop]: 16 mSDtfsCounter, 9 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:32,379 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 68 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:32,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2021-12-14 14:47:32,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 23. [2021-12-14 14:47:32,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.125) internal successors, (18), 16 states have internal predecessors, (18), 4 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-14 14:47:32,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 29 transitions. [2021-12-14 14:47:32,386 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 29 transitions. Word has length 19 [2021-12-14 14:47:32,386 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:32,386 INFO L470 AbstractCegarLoop]: Abstraction has 23 states and 29 transitions. [2021-12-14 14:47:32,387 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-14 14:47:32,387 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 29 transitions. [2021-12-14 14:47:32,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-14 14:47:32,388 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:32,388 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:32,389 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-12-14 14:47:32,389 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:32,389 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:32,389 INFO L85 PathProgramCache]: Analyzing trace with hash -445405100, now seen corresponding path program 1 times [2021-12-14 14:47:32,390 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:32,390 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1620640138] [2021-12-14 14:47:32,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:32,390 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:32,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,417 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:32,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,434 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:32,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,449 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 14:47:32,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,455 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-14 14:47:32,455 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:32,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1620640138] [2021-12-14 14:47:32,456 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1620640138] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:32,456 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1216491149] [2021-12-14 14:47:32,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:32,456 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:32,456 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:32,459 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:32,502 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-14 14:47:32,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:32,522 INFO L263 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-14 14:47:32,527 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:32,654 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 14:47:32,655 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:32,824 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-14 14:47:32,824 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1216491149] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:47:32,825 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 14:47:32,825 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 7] total 12 [2021-12-14 14:47:32,825 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [896519518] [2021-12-14 14:47:32,825 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 14:47:32,826 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-14 14:47:32,826 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:32,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-14 14:47:32,827 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2021-12-14 14:47:32,827 INFO L87 Difference]: Start difference. First operand 23 states and 29 transitions. Second operand has 12 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) [2021-12-14 14:47:32,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:32,928 INFO L93 Difference]: Finished difference Result 48 states and 75 transitions. [2021-12-14 14:47:32,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-14 14:47:32,929 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) Word has length 25 [2021-12-14 14:47:32,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:32,930 INFO L225 Difference]: With dead ends: 48 [2021-12-14 14:47:32,931 INFO L226 Difference]: Without dead ends: 30 [2021-12-14 14:47:32,931 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 49 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2021-12-14 14:47:32,932 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 55 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:32,933 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 85 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:32,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2021-12-14 14:47:32,944 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 25. [2021-12-14 14:47:32,944 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 17 states have (on average 1.1176470588235294) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (9), 5 states have call predecessors, (9), 4 states have call successors, (9) [2021-12-14 14:47:32,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 32 transitions. [2021-12-14 14:47:32,946 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 32 transitions. Word has length 25 [2021-12-14 14:47:32,946 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:32,946 INFO L470 AbstractCegarLoop]: Abstraction has 25 states and 32 transitions. [2021-12-14 14:47:32,947 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 12 states have internal predecessors, (31), 4 states have call successors, (5), 1 states have call predecessors, (5), 5 states have return successors, (5), 2 states have call predecessors, (5), 4 states have call successors, (5) [2021-12-14 14:47:32,947 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 32 transitions. [2021-12-14 14:47:32,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-12-14 14:47:32,951 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:32,951 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:32,969 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2021-12-14 14:47:33,161 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:33,161 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:33,162 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:33,162 INFO L85 PathProgramCache]: Analyzing trace with hash 1893657534, now seen corresponding path program 1 times [2021-12-14 14:47:33,162 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:33,162 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1440830776] [2021-12-14 14:47:33,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:33,163 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:33,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,202 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:33,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,258 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:33,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,299 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:33,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,348 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:33,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,404 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 14:47:33,405 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:33,405 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1440830776] [2021-12-14 14:47:33,405 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1440830776] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:33,405 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [90014481] [2021-12-14 14:47:33,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:33,406 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:33,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:33,407 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:33,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-14 14:47:33,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:33,445 INFO L263 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-14 14:47:33,447 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:33,546 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-12-14 14:47:33,546 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:34,145 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 15 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-14 14:47:34,145 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [90014481] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:47:34,145 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 14:47:34,145 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11, 13] total 25 [2021-12-14 14:47:34,146 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2050280963] [2021-12-14 14:47:34,146 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 14:47:34,146 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2021-12-14 14:47:34,146 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:34,147 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-12-14 14:47:34,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=520, Unknown=0, NotChecked=0, Total=600 [2021-12-14 14:47:34,147 INFO L87 Difference]: Start difference. First operand 25 states and 32 transitions. Second operand has 25 states, 25 states have (on average 1.48) internal successors, (37), 19 states have internal predecessors, (37), 3 states have call successors, (5), 1 states have call predecessors, (5), 8 states have return successors, (9), 8 states have call predecessors, (9), 3 states have call successors, (9) [2021-12-14 14:47:34,904 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:34,904 INFO L93 Difference]: Finished difference Result 72 states and 133 transitions. [2021-12-14 14:47:34,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2021-12-14 14:47:34,907 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 1.48) internal successors, (37), 19 states have internal predecessors, (37), 3 states have call successors, (5), 1 states have call predecessors, (5), 8 states have return successors, (9), 8 states have call predecessors, (9), 3 states have call successors, (9) Word has length 32 [2021-12-14 14:47:34,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:34,910 INFO L225 Difference]: With dead ends: 72 [2021-12-14 14:47:34,910 INFO L226 Difference]: Without dead ends: 66 [2021-12-14 14:47:34,911 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=423, Invalid=2027, Unknown=0, NotChecked=0, Total=2450 [2021-12-14 14:47:34,912 INFO L933 BasicCegarLoop]: 18 mSDtfsCounter, 50 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 542 mSolverCounterSat, 144 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 686 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 144 IncrementalHoareTripleChecker+Valid, 542 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:34,913 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 165 Invalid, 686 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [144 Valid, 542 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-14 14:47:34,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2021-12-14 14:47:34,925 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 38. [2021-12-14 14:47:34,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (31), 10 states have call predecessors, (31), 6 states have call successors, (31) [2021-12-14 14:47:34,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 64 transitions. [2021-12-14 14:47:34,927 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 64 transitions. Word has length 32 [2021-12-14 14:47:34,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:34,928 INFO L470 AbstractCegarLoop]: Abstraction has 38 states and 64 transitions. [2021-12-14 14:47:34,928 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 1.48) internal successors, (37), 19 states have internal predecessors, (37), 3 states have call successors, (5), 1 states have call predecessors, (5), 8 states have return successors, (9), 8 states have call predecessors, (9), 3 states have call successors, (9) [2021-12-14 14:47:34,928 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 64 transitions. [2021-12-14 14:47:34,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-12-14 14:47:34,930 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:34,930 INFO L514 BasicCegarLoop]: trace histogram [6, 6, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:34,956 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-14 14:47:35,143 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2021-12-14 14:47:35,144 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:35,144 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:35,144 INFO L85 PathProgramCache]: Analyzing trace with hash 372648096, now seen corresponding path program 2 times [2021-12-14 14:47:35,144 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:35,144 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1946230596] [2021-12-14 14:47:35,144 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:35,145 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:35,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,170 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:35,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,189 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:35,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,215 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:35,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,239 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:35,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,250 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:35,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,262 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:35,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:35,268 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 34 proven. 9 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2021-12-14 14:47:35,268 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:35,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1946230596] [2021-12-14 14:47:35,269 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1946230596] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:35,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1948118525] [2021-12-14 14:47:35,269 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-14 14:47:35,269 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:35,270 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:35,271 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:35,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-14 14:47:35,332 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-14 14:47:35,333 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:47:35,334 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-14 14:47:35,337 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:35,482 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 31 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-14 14:47:35,483 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:35,893 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 36 proven. 9 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-14 14:47:35,894 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1948118525] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:47:35,894 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 14:47:35,894 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 9] total 19 [2021-12-14 14:47:35,894 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [541107872] [2021-12-14 14:47:35,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 14:47:35,895 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-12-14 14:47:35,895 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:35,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-12-14 14:47:35,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=294, Unknown=0, NotChecked=0, Total=342 [2021-12-14 14:47:35,896 INFO L87 Difference]: Start difference. First operand 38 states and 64 transitions. Second operand has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 6 states have call successors, (8), 1 states have call predecessors, (8), 10 states have return successors, (13), 9 states have call predecessors, (13), 6 states have call successors, (13) [2021-12-14 14:47:36,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:36,177 INFO L93 Difference]: Finished difference Result 96 states and 220 transitions. [2021-12-14 14:47:36,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-14 14:47:36,179 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 6 states have call successors, (8), 1 states have call predecessors, (8), 10 states have return successors, (13), 9 states have call predecessors, (13), 6 states have call successors, (13) Word has length 46 [2021-12-14 14:47:36,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:36,180 INFO L225 Difference]: With dead ends: 96 [2021-12-14 14:47:36,180 INFO L226 Difference]: Without dead ends: 63 [2021-12-14 14:47:36,182 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=168, Invalid=644, Unknown=0, NotChecked=0, Total=812 [2021-12-14 14:47:36,183 INFO L933 BasicCegarLoop]: 15 mSDtfsCounter, 63 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 78 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 78 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:36,183 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [63 Valid, 104 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [78 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:36,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2021-12-14 14:47:36,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 60. [2021-12-14 14:47:36,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 39 states have (on average 1.0512820512820513) internal successors, (41), 40 states have internal predecessors, (41), 9 states have call successors, (9), 2 states have call predecessors, (9), 11 states have return successors, (57), 17 states have call predecessors, (57), 9 states have call successors, (57) [2021-12-14 14:47:36,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 107 transitions. [2021-12-14 14:47:36,211 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 107 transitions. Word has length 46 [2021-12-14 14:47:36,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:36,212 INFO L470 AbstractCegarLoop]: Abstraction has 60 states and 107 transitions. [2021-12-14 14:47:36,212 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 17 states have internal predecessors, (45), 6 states have call successors, (8), 1 states have call predecessors, (8), 10 states have return successors, (13), 9 states have call predecessors, (13), 6 states have call successors, (13) [2021-12-14 14:47:36,212 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 107 transitions. [2021-12-14 14:47:36,215 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2021-12-14 14:47:36,215 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:36,215 INFO L514 BasicCegarLoop]: trace histogram [9, 9, 6, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:36,241 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-14 14:47:36,438 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:36,439 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:36,439 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:36,439 INFO L85 PathProgramCache]: Analyzing trace with hash 421612277, now seen corresponding path program 3 times [2021-12-14 14:47:36,439 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:36,439 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069589585] [2021-12-14 14:47:36,439 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:36,440 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:36,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,491 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:36,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,523 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,560 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,580 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,602 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,622 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,659 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:36,661 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,688 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-14 14:47:36,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,707 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:36,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:36,712 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 76 proven. 29 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2021-12-14 14:47:36,712 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:36,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069589585] [2021-12-14 14:47:36,712 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2069589585] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:36,712 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1448593036] [2021-12-14 14:47:36,712 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-14 14:47:36,712 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:36,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:36,714 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:36,715 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-14 14:47:36,775 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-12-14 14:47:36,775 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:47:36,776 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-14 14:47:36,781 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:36,935 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 53 proven. 6 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2021-12-14 14:47:36,935 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:37,536 INFO L134 CoverageAnalysis]: Checked inductivity of 175 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 116 trivial. 0 not checked. [2021-12-14 14:47:37,536 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1448593036] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:37,537 INFO L186 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2021-12-14 14:47:37,537 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [16, 9] total 27 [2021-12-14 14:47:37,537 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2104595102] [2021-12-14 14:47:37,537 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 14:47:37,538 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-12-14 14:47:37,538 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:37,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-14 14:47:37,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=620, Unknown=0, NotChecked=0, Total=702 [2021-12-14 14:47:37,539 INFO L87 Difference]: Start difference. First operand 60 states and 107 transitions. Second operand has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 6 states have internal predecessors, (22), 1 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (7), 4 states have call predecessors, (7), 1 states have call successors, (7) [2021-12-14 14:47:37,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:37,661 INFO L93 Difference]: Finished difference Result 76 states and 139 transitions. [2021-12-14 14:47:37,666 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-14 14:47:37,666 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 6 states have internal predecessors, (22), 1 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (7), 4 states have call predecessors, (7), 1 states have call successors, (7) Word has length 66 [2021-12-14 14:47:37,667 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:37,668 INFO L225 Difference]: With dead ends: 76 [2021-12-14 14:47:37,668 INFO L226 Difference]: Without dead ends: 72 [2021-12-14 14:47:37,669 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 140 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=101, Invalid=829, Unknown=0, NotChecked=0, Total=930 [2021-12-14 14:47:37,670 INFO L933 BasicCegarLoop]: 16 mSDtfsCounter, 9 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:37,670 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 80 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:37,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2021-12-14 14:47:37,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 72. [2021-12-14 14:47:37,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 47 states have (on average 1.0425531914893618) internal successors, (49), 48 states have internal predecessors, (49), 9 states have call successors, (9), 2 states have call predecessors, (9), 15 states have return successors, (75), 21 states have call predecessors, (75), 9 states have call successors, (75) [2021-12-14 14:47:37,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 133 transitions. [2021-12-14 14:47:37,690 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 133 transitions. Word has length 66 [2021-12-14 14:47:37,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:37,690 INFO L470 AbstractCegarLoop]: Abstraction has 72 states and 133 transitions. [2021-12-14 14:47:37,690 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.4444444444444446) internal successors, (22), 6 states have internal predecessors, (22), 1 states have call successors, (4), 1 states have call predecessors, (4), 3 states have return successors, (7), 4 states have call predecessors, (7), 1 states have call successors, (7) [2021-12-14 14:47:37,691 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 133 transitions. [2021-12-14 14:47:37,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2021-12-14 14:47:37,693 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:37,693 INFO L514 BasicCegarLoop]: trace histogram [12, 12, 8, 5, 5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:37,712 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-14 14:47:37,903 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:37,903 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:37,904 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:37,904 INFO L85 PathProgramCache]: Analyzing trace with hash -558645120, now seen corresponding path program 4 times [2021-12-14 14:47:37,904 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:37,904 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [903583675] [2021-12-14 14:47:37,904 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:37,905 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:37,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:37,931 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:37,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:37,953 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:37,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:37,975 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:37,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:37,993 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:37,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,006 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:38,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,010 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:38,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,013 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:38,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,022 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-14 14:47:38,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,038 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:38,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,075 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:38,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,083 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:38,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,089 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:38,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:38,093 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 136 proven. 61 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2021-12-14 14:47:38,094 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:38,094 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [903583675] [2021-12-14 14:47:38,094 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [903583675] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:38,094 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [643238025] [2021-12-14 14:47:38,094 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-14 14:47:38,094 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:38,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:38,096 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:38,097 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-14 14:47:38,162 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-14 14:47:38,162 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:47:38,163 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 18 conjunts are in the unsatisfiable core [2021-12-14 14:47:38,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:38,364 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 111 proven. 112 refuted. 0 times theorem prover too weak. 101 trivial. 0 not checked. [2021-12-14 14:47:38,364 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:39,664 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 111 proven. 128 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2021-12-14 14:47:39,664 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [643238025] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:47:39,664 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 14:47:39,665 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 15] total 20 [2021-12-14 14:47:39,665 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [994878242] [2021-12-14 14:47:39,665 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 14:47:39,665 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-12-14 14:47:39,666 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:39,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-12-14 14:47:39,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=292, Unknown=0, NotChecked=0, Total=380 [2021-12-14 14:47:39,667 INFO L87 Difference]: Start difference. First operand 72 states and 133 transitions. Second operand has 20 states, 20 states have (on average 3.4) internal successors, (68), 20 states have internal predecessors, (68), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 9 states have call predecessors, (26), 12 states have call successors, (26) [2021-12-14 14:47:39,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:39,871 INFO L93 Difference]: Finished difference Result 156 states and 445 transitions. [2021-12-14 14:47:39,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-14 14:47:39,874 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 3.4) internal successors, (68), 20 states have internal predecessors, (68), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 9 states have call predecessors, (26), 12 states have call successors, (26) Word has length 86 [2021-12-14 14:47:39,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:39,876 INFO L225 Difference]: With dead ends: 156 [2021-12-14 14:47:39,877 INFO L226 Difference]: Without dead ends: 89 [2021-12-14 14:47:39,879 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 190 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=183, Invalid=467, Unknown=0, NotChecked=0, Total=650 [2021-12-14 14:47:39,879 INFO L933 BasicCegarLoop]: 28 mSDtfsCounter, 90 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 195 mSolverCounterSat, 128 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 128 IncrementalHoareTripleChecker+Valid, 195 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:39,880 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [98 Valid, 163 Invalid, 323 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [128 Valid, 195 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-14 14:47:39,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2021-12-14 14:47:39,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 72. [2021-12-14 14:47:39,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 48 states have (on average 1.1041666666666667) internal successors, (53), 50 states have internal predecessors, (53), 10 states have call successors, (10), 5 states have call predecessors, (10), 13 states have return successors, (60), 16 states have call predecessors, (60), 10 states have call successors, (60) [2021-12-14 14:47:39,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 123 transitions. [2021-12-14 14:47:39,894 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 123 transitions. Word has length 86 [2021-12-14 14:47:39,894 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:39,894 INFO L470 AbstractCegarLoop]: Abstraction has 72 states and 123 transitions. [2021-12-14 14:47:39,894 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 3.4) internal successors, (68), 20 states have internal predecessors, (68), 12 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 9 states have call predecessors, (26), 12 states have call successors, (26) [2021-12-14 14:47:39,895 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 123 transitions. [2021-12-14 14:47:39,896 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2021-12-14 14:47:39,896 INFO L506 BasicCegarLoop]: Found error trace [2021-12-14 14:47:39,896 INFO L514 BasicCegarLoop]: trace histogram [16, 16, 11, 7, 7, 7, 7, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 14:47:39,915 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-14 14:47:40,107 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:40,108 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-14 14:47:40,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 14:47:40,108 INFO L85 PathProgramCache]: Analyzing trace with hash 1617123443, now seen corresponding path program 5 times [2021-12-14 14:47:40,108 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 14:47:40,108 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [115320893] [2021-12-14 14:47:40,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 14:47:40,108 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 14:47:40,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,142 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 14:47:40,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,177 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,232 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,247 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,277 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,287 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,311 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,317 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,327 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:40,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,330 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-14 14:47:40,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,334 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,336 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 63 [2021-12-14 14:47:40,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,343 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,346 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,349 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 14:47:40,349 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,351 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-14 14:47:40,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 14:47:40,353 INFO L134 CoverageAnalysis]: Checked inductivity of 601 backedges. 104 proven. 217 refuted. 0 times theorem prover too weak. 280 trivial. 0 not checked. [2021-12-14 14:47:40,353 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 14:47:40,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [115320893] [2021-12-14 14:47:40,354 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [115320893] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 14:47:40,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [445503569] [2021-12-14 14:47:40,354 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-14 14:47:40,354 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:40,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 14:47:40,355 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-14 14:47:40,363 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-14 14:47:40,431 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2021-12-14 14:47:40,432 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 14:47:40,432 INFO L263 TraceCheckSpWp]: Trace formula consists of 170 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 14:47:40,435 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 14:47:40,683 INFO L134 CoverageAnalysis]: Checked inductivity of 601 backedges. 337 proven. 37 refuted. 0 times theorem prover too weak. 227 trivial. 0 not checked. [2021-12-14 14:47:40,683 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 14:47:42,374 INFO L134 CoverageAnalysis]: Checked inductivity of 601 backedges. 148 proven. 142 refuted. 0 times theorem prover too weak. 311 trivial. 0 not checked. [2021-12-14 14:47:42,375 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [445503569] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 14:47:42,375 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 14:47:42,375 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 15] total 34 [2021-12-14 14:47:42,376 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2103596747] [2021-12-14 14:47:42,376 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 14:47:42,377 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2021-12-14 14:47:42,377 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 14:47:42,377 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2021-12-14 14:47:42,378 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=1002, Unknown=0, NotChecked=0, Total=1122 [2021-12-14 14:47:42,378 INFO L87 Difference]: Start difference. First operand 72 states and 123 transitions. Second operand has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 12 states have call successors, (19), 2 states have call predecessors, (19), 15 states have return successors, (34), 20 states have call predecessors, (34), 12 states have call successors, (34) [2021-12-14 14:47:43,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 14:47:43,426 INFO L93 Difference]: Finished difference Result 142 states and 351 transitions. [2021-12-14 14:47:43,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2021-12-14 14:47:43,427 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 12 states have call successors, (19), 2 states have call predecessors, (19), 15 states have return successors, (34), 20 states have call predecessors, (34), 12 states have call successors, (34) Word has length 113 [2021-12-14 14:47:43,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-14 14:47:43,427 INFO L225 Difference]: With dead ends: 142 [2021-12-14 14:47:43,428 INFO L226 Difference]: Without dead ends: 0 [2021-12-14 14:47:43,430 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 301 GetRequests, 238 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 746 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=778, Invalid=3382, Unknown=0, NotChecked=0, Total=4160 [2021-12-14 14:47:43,431 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 41 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 1103 mSolverCounterSat, 147 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 1250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 147 IncrementalHoareTripleChecker+Valid, 1103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-14 14:47:43,431 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 186 Invalid, 1250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [147 Valid, 1103 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-14 14:47:43,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2021-12-14 14:47:43,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2021-12-14 14:47:43,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-14 14:47:43,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2021-12-14 14:47:43,432 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 113 [2021-12-14 14:47:43,432 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-14 14:47:43,432 INFO L470 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-14 14:47:43,432 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 2.264705882352941) internal successors, (77), 28 states have internal predecessors, (77), 12 states have call successors, (19), 2 states have call predecessors, (19), 15 states have return successors, (34), 20 states have call predecessors, (34), 12 states have call successors, (34) [2021-12-14 14:47:43,433 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2021-12-14 14:47:43,433 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2021-12-14 14:47:43,435 INFO L764 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2021-12-14 14:47:43,458 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-14 14:47:43,651 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 14:47:43,653 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2021-12-14 14:47:44,502 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point L-1(line -1) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point L30(lines 30 34) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startENTRY(line -1) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L861 garLoopResultBuilder]: At program point L28(lines 28 48) the Hoare annotation is: true [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION(line 46) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point L46(line 46) no Hoare annotation was computed. [2021-12-14 14:47:44,503 INFO L858 garLoopResultBuilder]: For program point L43(lines 43 47) no Hoare annotation was computed. [2021-12-14 14:47:44,504 INFO L854 garLoopResultBuilder]: At program point L42(line 42) the Hoare annotation is: (and (<= |ULTIMATE.start_main_~m~0#1| 3) (<= 0 |ULTIMATE.start_main_~n~0#1|)) [2021-12-14 14:47:44,504 INFO L858 garLoopResultBuilder]: For program point L42-1(line 42) no Hoare annotation was computed. [2021-12-14 14:47:44,504 INFO L858 garLoopResultBuilder]: For program point L36(lines 36 41) no Hoare annotation was computed. [2021-12-14 14:47:44,504 INFO L858 garLoopResultBuilder]: For program point ackermannEXIT(lines 17 25) no Hoare annotation was computed. [2021-12-14 14:47:44,504 INFO L854 garLoopResultBuilder]: At program point L24(line 24) the Hoare annotation is: (and (not (= ackermann_~m 0)) (= ackermann_~n |ackermann_#in~n|) (= ackermann_~m |ackermann_#in~m|)) [2021-12-14 14:47:44,504 INFO L858 garLoopResultBuilder]: For program point L24-1(line 24) no Hoare annotation was computed. [2021-12-14 14:47:44,504 INFO L854 garLoopResultBuilder]: At program point L22(line 22) the Hoare annotation is: (and (= ackermann_~n |ackermann_#in~n|) (= ackermann_~m |ackermann_#in~m|) (not (= |ackermann_#in~m| 0)) (<= |ackermann_#in~n| 0)) [2021-12-14 14:47:44,504 INFO L854 garLoopResultBuilder]: At program point L24-2(line 24) the Hoare annotation is: (and (not (= ackermann_~m 0)) (<= 0 |ackermann_#in~m|) (= ackermann_~n |ackermann_#in~n|) (<= 2 |ackermann_#t~ret5|) (= ackermann_~m |ackermann_#in~m|) (or (<= 3 |ackermann_#t~ret5|) (not (<= 2 |ackermann_#in~m|)))) [2021-12-14 14:47:44,504 INFO L861 garLoopResultBuilder]: At program point ackermannENTRY(lines 17 25) the Hoare annotation is: true [2021-12-14 14:47:44,505 INFO L858 garLoopResultBuilder]: For program point L21(lines 21 23) no Hoare annotation was computed. [2021-12-14 14:47:44,505 INFO L858 garLoopResultBuilder]: For program point L22-1(line 22) no Hoare annotation was computed. [2021-12-14 14:47:44,505 INFO L858 garLoopResultBuilder]: For program point L24-3(line 24) no Hoare annotation was computed. [2021-12-14 14:47:44,505 INFO L858 garLoopResultBuilder]: For program point L18(lines 18 20) no Hoare annotation was computed. [2021-12-14 14:47:44,505 INFO L858 garLoopResultBuilder]: For program point ackermannFINAL(lines 17 25) no Hoare annotation was computed. [2021-12-14 14:47:44,507 INFO L732 BasicCegarLoop]: Path program histogram: [5, 1, 1, 1] [2021-12-14 14:47:44,509 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2021-12-14 14:47:44,518 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.12 02:47:44 BoogieIcfgContainer [2021-12-14 14:47:44,518 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-12-14 14:47:44,519 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-14 14:47:44,519 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-14 14:47:44,519 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-14 14:47:44,519 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 02:47:31" (3/4) ... [2021-12-14 14:47:44,521 INFO L137 WitnessPrinter]: Generating witness for correct program [2021-12-14 14:47:44,527 INFO L354 RCFGBacktranslator]: Ignoring RootEdge to procedure ackermann [2021-12-14 14:47:44,531 INFO L910 BoogieBacktranslator]: Reduced CFG by removing 11 nodes and edges [2021-12-14 14:47:44,531 INFO L910 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2021-12-14 14:47:44,532 INFO L910 BoogieBacktranslator]: Reduced CFG by removing 2 nodes and edges [2021-12-14 14:47:44,532 INFO L910 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2021-12-14 14:47:44,561 INFO L141 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2021-12-14 14:47:44,561 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-14 14:47:44,561 INFO L158 Benchmark]: Toolchain (without parser) took 13632.72ms. Allocated memory was 100.7MB in the beginning and 176.2MB in the end (delta: 75.5MB). Free memory was 68.5MB in the beginning and 121.9MB in the end (delta: -53.4MB). Peak memory consumption was 21.0MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,562 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 81.8MB. Free memory was 51.4MB in the beginning and 51.4MB in the end (delta: 27.0kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 14:47:44,562 INFO L158 Benchmark]: CACSL2BoogieTranslator took 221.37ms. Allocated memory is still 100.7MB. Free memory was 68.5MB in the beginning and 77.4MB in the end (delta: -8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,562 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.22ms. Allocated memory is still 100.7MB. Free memory was 77.4MB in the beginning and 75.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,562 INFO L158 Benchmark]: Boogie Preprocessor took 13.06ms. Allocated memory is still 100.7MB. Free memory was 75.8MB in the beginning and 74.6MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 14:47:44,563 INFO L158 Benchmark]: RCFGBuilder took 266.63ms. Allocated memory is still 100.7MB. Free memory was 74.6MB in the beginning and 65.3MB in the end (delta: 9.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,563 INFO L158 Benchmark]: TraceAbstraction took 13060.23ms. Allocated memory was 100.7MB in the beginning and 176.2MB in the end (delta: 75.5MB). Free memory was 64.8MB in the beginning and 125.1MB in the end (delta: -60.3MB). Peak memory consumption was 92.8MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,564 INFO L158 Benchmark]: Witness Printer took 42.35ms. Allocated memory is still 176.2MB. Free memory was 125.1MB in the beginning and 121.9MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-14 14:47:44,565 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.10ms. Allocated memory is still 81.8MB. Free memory was 51.4MB in the beginning and 51.4MB in the end (delta: 27.0kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 221.37ms. Allocated memory is still 100.7MB. Free memory was 68.5MB in the beginning and 77.4MB in the end (delta: -8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.22ms. Allocated memory is still 100.7MB. Free memory was 77.4MB in the beginning and 75.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 13.06ms. Allocated memory is still 100.7MB. Free memory was 75.8MB in the beginning and 74.6MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 266.63ms. Allocated memory is still 100.7MB. Free memory was 74.6MB in the beginning and 65.3MB in the end (delta: 9.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 13060.23ms. Allocated memory was 100.7MB in the beginning and 176.2MB in the end (delta: 75.5MB). Free memory was 64.8MB in the beginning and 125.1MB in the end (delta: -60.3MB). Peak memory consumption was 92.8MB. Max. memory is 16.1GB. * Witness Printer took 42.35ms. Allocated memory is still 176.2MB. Free memory was 125.1MB in the beginning and 121.9MB in the end (delta: 3.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 46]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 23 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 13.0s, OverallIterations: 8, TraceHistogramMax: 16, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 2.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.9s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 371 SdHoareTripleChecker+Valid, 1.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 338 mSDsluCounter, 942 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 780 mSDsCounter, 560 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2327 IncrementalHoareTripleChecker+Invalid, 2887 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 560 mSolverCounterUnsat, 162 mSDtfsCounter, 2327 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1010 GetRequests, 784 SyntacticMatches, 4 SemanticMatches, 222 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1496 ImplicationChecksByTransitivity, 2.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=72occurred in iteration=6, InterpolantAutomatonStates: 128, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 55 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 6 LocationsWithAnnotation, 166 PreInvPairs, 253 NumberOfFragments, 59 HoareAnnotationTreeSize, 166 FomulaSimplifications, 4733 FormulaSimplificationTreeSizeReduction, 0.5s HoareSimplificationTime, 6 FomulaSimplificationsInter, 8077 FormulaSimplificationTreeSizeReductionInter, 0.4s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 7.1s InterpolantComputationTime, 767 NumberOfCodeBlocks, 669 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 1115 ConstructedInterpolants, 0 QuantifiedInterpolants, 2309 SizeOfPredicates, 20 NumberOfNonLiveVariables, 882 ConjunctsInSsa, 76 ConjunctsInUnsatCore, 20 InterpolantComputations, 3 PerfectInterpolantSequences, 2845/3631 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 28]: Loop Invariant Derived loop invariant: 1 RESULT: Ultimate proved your program to be correct! [2021-12-14 14:47:44,609 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE