./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive/recHanoi03-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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/recHanoi03-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 --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 6256a35b65d93a8e45ad38c9510c3be689a890aeee58265a5723be13a7385a72 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 23:20:02,673 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 23:20:02,750 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 23:20:02,753 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 23:20:02,754 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 23:20:02,782 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 23:20:02,783 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 23:20:02,784 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 23:20:02,785 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 23:20:02,786 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 23:20:02,787 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 23:20:02,787 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 23:20:02,788 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 23:20:02,790 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 23:20:02,790 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 23:20:02,790 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 23:20:02,791 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 23:20:02,791 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 23:20:02,791 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 23:20:02,791 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 23:20:02,795 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 23:20:02,796 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 23:20:02,796 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 23:20:02,796 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 23:20:02,796 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 23:20:02,796 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 23:20:02,797 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 23:20:02,797 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 23:20:02,797 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 23:20:02,797 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 23:20:02,798 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 23:20:02,798 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 23:20:02,798 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 23:20:02,798 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 23:20:02,799 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 23:20:02,799 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 23:20:02,799 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 23:20:02,799 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 23:20:02,799 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 23:20:02,800 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 23:20:02,800 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 23:20:02,800 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 23:20:02,801 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 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 -> 6256a35b65d93a8e45ad38c9510c3be689a890aeee58265a5723be13a7385a72 [2024-11-09 23:20:03,040 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 23:20:03,063 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 23:20:03,066 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 23:20:03,067 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 23:20:03,068 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 23:20:03,069 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/recHanoi03-2.c [2024-11-09 23:20:04,493 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 23:20:04,677 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 23:20:04,678 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/recHanoi03-2.c [2024-11-09 23:20:04,685 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/255c7defd/190c8493d06b4044b94d283d94f2868e/FLAG9c8434f00 [2024-11-09 23:20:05,077 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/255c7defd/190c8493d06b4044b94d283d94f2868e [2024-11-09 23:20:05,080 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 23:20:05,082 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 23:20:05,086 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 23:20:05,086 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 23:20:05,091 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 23:20:05,093 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,094 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4b56e2b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05, skipping insertion in model container [2024-11-09 23:20:05,094 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,111 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 23:20:05,282 WARN L250 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/recHanoi03-2.c[769,782] [2024-11-09 23:20:05,286 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 23:20:05,294 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 23:20:05,313 WARN L250 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/recHanoi03-2.c[769,782] [2024-11-09 23:20:05,319 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 23:20:05,351 INFO L204 MainTranslator]: Completed translation [2024-11-09 23:20:05,352 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05 WrapperNode [2024-11-09 23:20:05,352 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 23:20:05,353 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 23:20:05,353 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 23:20:05,354 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 23:20:05,362 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,367 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,381 INFO L138 Inliner]: procedures = 13, calls = 9, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 26 [2024-11-09 23:20:05,381 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 23:20:05,382 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 23:20:05,382 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 23:20:05,382 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 23:20:05,390 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,390 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,391 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,402 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 23:20:05,402 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,402 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,405 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,405 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,406 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,406 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,407 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 23:20:05,408 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 23:20:05,408 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 23:20:05,409 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 23:20:05,409 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (1/1) ... [2024-11-09 23:20:05,416 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 23:20:05,424 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:05,438 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 23:20:05,441 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 23:20:05,478 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 23:20:05,479 INFO L130 BoogieDeclarations]: Found specification of procedure hanoi [2024-11-09 23:20:05,479 INFO L138 BoogieDeclarations]: Found implementation of procedure hanoi [2024-11-09 23:20:05,479 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 23:20:05,479 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 23:20:05,479 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 23:20:05,534 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 23:20:05,535 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 23:20:05,589 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4; [2024-11-09 23:20:05,634 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2024-11-09 23:20:05,634 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 23:20:05,644 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 23:20:05,644 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 23:20:05,645 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 11:20:05 BoogieIcfgContainer [2024-11-09 23:20:05,645 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 23:20:05,647 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 23:20:05,647 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 23:20:05,650 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 23:20:05,651 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 11:20:05" (1/3) ... [2024-11-09 23:20:05,652 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@634d01a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 11:20:05, skipping insertion in model container [2024-11-09 23:20:05,652 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 11:20:05" (2/3) ... [2024-11-09 23:20:05,653 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@634d01a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 11:20:05, skipping insertion in model container [2024-11-09 23:20:05,653 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 11:20:05" (3/3) ... [2024-11-09 23:20:05,654 INFO L112 eAbstractionObserver]: Analyzing ICFG recHanoi03-2.c [2024-11-09 23:20:05,671 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 23:20:05,673 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 23:20:05,729 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 23:20:05,735 INFO L333 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, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@383fe8c6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 23:20:05,735 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 23:20:05,738 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-09 23:20:05,743 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-09 23:20:05,743 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:05,744 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:05,744 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:05,748 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:05,748 INFO L85 PathProgramCache]: Analyzing trace with hash 2145442678, now seen corresponding path program 1 times [2024-11-09 23:20:05,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:05,757 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [812099137] [2024-11-09 23:20:05,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:05,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:05,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,023 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:06,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,102 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 23:20:06,103 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:06,103 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [812099137] [2024-11-09 23:20:06,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [812099137] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 23:20:06,104 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 23:20:06,104 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 23:20:06,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [924053872] [2024-11-09 23:20:06,106 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 23:20:06,110 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 23:20:06,110 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:06,127 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 23:20:06,127 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 23:20:06,129 INFO L87 Difference]: Start difference. First operand has 19 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 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) [2024-11-09 23:20:06,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:06,253 INFO L93 Difference]: Finished difference Result 29 states and 33 transitions. [2024-11-09 23:20:06,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 23:20:06,257 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 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 [2024-11-09 23:20:06,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:06,264 INFO L225 Difference]: With dead ends: 29 [2024-11-09 23:20:06,265 INFO L226 Difference]: Without dead ends: 17 [2024-11-09 23:20:06,268 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-09 23:20:06,274 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 3 mSDsluCounter, 38 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:06,275 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 53 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 23:20:06,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2024-11-09 23:20:06,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2024-11-09 23:20:06,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 12 states have (on average 1.0833333333333333) internal successors, (13), 13 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 23:20:06,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2024-11-09 23:20:06,322 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 12 [2024-11-09 23:20:06,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:06,324 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 18 transitions. [2024-11-09 23:20:06,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 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) [2024-11-09 23:20:06,324 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 18 transitions. [2024-11-09 23:20:06,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-09 23:20:06,326 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:06,326 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:06,327 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 23:20:06,327 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:06,328 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:06,330 INFO L85 PathProgramCache]: Analyzing trace with hash -803054127, now seen corresponding path program 1 times [2024-11-09 23:20:06,330 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:06,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1110912967] [2024-11-09 23:20:06,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:06,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:06,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:06,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,661 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:06,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,759 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 23:20:06,760 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:06,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1110912967] [2024-11-09 23:20:06,761 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1110912967] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:20:06,761 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1355109875] [2024-11-09 23:20:06,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:06,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:06,762 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:06,764 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) [2024-11-09 23:20:06,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 23:20:06,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:06,825 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 23:20:06,839 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:20:07,018 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 23:20:07,018 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:20:07,430 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 23:20:07,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1355109875] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:20:07,431 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 23:20:07,431 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 20 [2024-11-09 23:20:07,434 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [326882765] [2024-11-09 23:20:07,434 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 23:20:07,435 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-09 23:20:07,435 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:07,436 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-09 23:20:07,436 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=316, Unknown=0, NotChecked=0, Total=380 [2024-11-09 23:20:07,437 INFO L87 Difference]: Start difference. First operand 17 states and 18 transitions. Second operand has 20 states, 20 states have (on average 1.45) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 5 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 23:20:07,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:07,612 INFO L93 Difference]: Finished difference Result 30 states and 32 transitions. [2024-11-09 23:20:07,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 23:20:07,614 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.45) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 5 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) Word has length 18 [2024-11-09 23:20:07,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:07,614 INFO L225 Difference]: With dead ends: 30 [2024-11-09 23:20:07,615 INFO L226 Difference]: Without dead ends: 23 [2024-11-09 23:20:07,615 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=98, Invalid=454, Unknown=0, NotChecked=0, Total=552 [2024-11-09 23:20:07,616 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 6 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:07,619 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 107 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 23:20:07,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-09 23:20:07,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-09 23:20:07,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.0625) internal successors, (17), 17 states have internal predecessors, (17), 2 states have call successors, (2), 1 states have call predecessors, (2), 4 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 23:20:07,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2024-11-09 23:20:07,627 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 18 [2024-11-09 23:20:07,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:07,627 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 24 transitions. [2024-11-09 23:20:07,628 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.45) internal successors, (29), 14 states have internal predecessors, (29), 4 states have call successors, (4), 1 states have call predecessors, (4), 5 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 23:20:07,628 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 24 transitions. [2024-11-09 23:20:07,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-09 23:20:07,629 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:07,629 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:07,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 23:20:07,833 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:07,834 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:07,834 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:07,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1505065807, now seen corresponding path program 2 times [2024-11-09 23:20:07,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:07,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [276758845] [2024-11-09 23:20:07,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:07,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:07,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:07,939 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:07,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:08,028 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:08,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:08,101 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:08,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:08,166 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:08,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:08,215 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-09 23:20:08,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:08,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [276758845] [2024-11-09 23:20:08,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [276758845] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:20:08,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1429843841] [2024-11-09 23:20:08,217 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 23:20:08,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:08,218 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:08,220 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) [2024-11-09 23:20:08,221 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 23:20:08,264 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 23:20:08,265 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 23:20:08,266 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 23:20:08,269 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:20:08,553 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-09 23:20:08,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:20:09,648 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 23:20:09,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1429843841] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:20:09,648 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 23:20:09,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 15] total 30 [2024-11-09 23:20:09,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [966883827] [2024-11-09 23:20:09,649 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 23:20:09,649 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-09 23:20:09,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:09,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-09 23:20:09,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=753, Unknown=0, NotChecked=0, Total=870 [2024-11-09 23:20:09,651 INFO L87 Difference]: Start difference. First operand 23 states and 24 transitions. Second operand has 30 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 9 states have return successors, (12), 10 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 23:20:09,951 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:09,952 INFO L93 Difference]: Finished difference Result 39 states and 42 transitions. [2024-11-09 23:20:09,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-09 23:20:09,952 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 9 states have return successors, (12), 10 states have call predecessors, (12), 6 states have call successors, (12) Word has length 30 [2024-11-09 23:20:09,953 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:09,953 INFO L225 Difference]: With dead ends: 39 [2024-11-09 23:20:09,953 INFO L226 Difference]: Without dead ends: 32 [2024-11-09 23:20:09,954 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 244 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=235, Invalid=1325, Unknown=0, NotChecked=0, Total=1560 [2024-11-09 23:20:09,955 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 18 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:09,956 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 160 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 233 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 23:20:09,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-09 23:20:09,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-09 23:20:09,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 23 states have internal predecessors, (23), 2 states have call successors, (2), 1 states have call predecessors, (2), 7 states have return successors, (8), 7 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-09 23:20:09,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 33 transitions. [2024-11-09 23:20:09,964 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 33 transitions. Word has length 30 [2024-11-09 23:20:09,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:09,966 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 33 transitions. [2024-11-09 23:20:09,966 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 20 states have internal predecessors, (41), 6 states have call successors, (6), 1 states have call predecessors, (6), 9 states have return successors, (12), 10 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-09 23:20:09,967 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 33 transitions. [2024-11-09 23:20:09,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-09 23:20:09,969 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:09,969 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:09,986 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 23:20:10,171 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-09 23:20:10,172 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:10,172 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:10,172 INFO L85 PathProgramCache]: Analyzing trace with hash 1290598614, now seen corresponding path program 3 times [2024-11-09 23:20:10,173 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:10,173 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2067928698] [2024-11-09 23:20:10,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:10,173 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:10,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,380 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:10,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,515 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:10,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,648 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:10,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:10,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,857 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:10,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:10,948 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:10,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:11,014 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:11,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:11,068 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2024-11-09 23:20:11,070 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:11,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2067928698] [2024-11-09 23:20:11,071 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2067928698] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:20:11,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1236517667] [2024-11-09 23:20:11,071 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 23:20:11,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:11,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:11,074 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) [2024-11-09 23:20:11,075 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 23:20:11,135 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-09 23:20:11,135 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 23:20:11,137 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-09 23:20:11,139 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:20:11,625 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2024-11-09 23:20:11,626 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:20:15,175 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 0 proven. 93 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-09 23:20:15,176 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1236517667] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:20:15,176 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 23:20:15,176 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18, 24] total 45 [2024-11-09 23:20:15,176 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631973627] [2024-11-09 23:20:15,177 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 23:20:15,177 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 45 states [2024-11-09 23:20:15,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:15,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2024-11-09 23:20:15,179 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=225, Invalid=1755, Unknown=0, NotChecked=0, Total=1980 [2024-11-09 23:20:15,180 INFO L87 Difference]: Start difference. First operand 32 states and 33 transitions. Second operand has 45 states, 45 states have (on average 1.3111111111111111) internal successors, (59), 29 states have internal predecessors, (59), 9 states have call successors, (9), 1 states have call predecessors, (9), 15 states have return successors, (21), 16 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-09 23:20:15,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:15,713 INFO L93 Difference]: Finished difference Result 57 states and 63 transitions. [2024-11-09 23:20:15,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-11-09 23:20:15,714 INFO L78 Accepts]: Start accepts. Automaton has has 45 states, 45 states have (on average 1.3111111111111111) internal successors, (59), 29 states have internal predecessors, (59), 9 states have call successors, (9), 1 states have call predecessors, (9), 15 states have return successors, (21), 16 states have call predecessors, (21), 9 states have call successors, (21) Word has length 48 [2024-11-09 23:20:15,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:15,715 INFO L225 Difference]: With dead ends: 57 [2024-11-09 23:20:15,715 INFO L226 Difference]: Without dead ends: 50 [2024-11-09 23:20:15,718 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 784 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=598, Invalid=3824, Unknown=0, NotChecked=0, Total=4422 [2024-11-09 23:20:15,718 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 80 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 446 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 302 SdHoareTripleChecker+Invalid, 477 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 446 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:15,719 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 302 Invalid, 477 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 446 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 23:20:15,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-11-09 23:20:15,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2024-11-09 23:20:15,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 35 states have internal predecessors, (35), 2 states have call successors, (2), 1 states have call predecessors, (2), 13 states have return successors, (14), 13 states have call predecessors, (14), 2 states have call successors, (14) [2024-11-09 23:20:15,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 51 transitions. [2024-11-09 23:20:15,728 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 51 transitions. Word has length 48 [2024-11-09 23:20:15,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:15,728 INFO L471 AbstractCegarLoop]: Abstraction has 50 states and 51 transitions. [2024-11-09 23:20:15,728 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 45 states, 45 states have (on average 1.3111111111111111) internal successors, (59), 29 states have internal predecessors, (59), 9 states have call successors, (9), 1 states have call predecessors, (9), 15 states have return successors, (21), 16 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-09 23:20:15,729 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 51 transitions. [2024-11-09 23:20:15,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-09 23:20:15,732 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:15,732 INFO L215 NwaCegarLoop]: trace histogram [13, 13, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:15,744 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 23:20:15,933 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:15,933 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:15,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:15,934 INFO L85 PathProgramCache]: Analyzing trace with hash 1802485302, now seen corresponding path program 4 times [2024-11-09 23:20:15,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:15,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1305281454] [2024-11-09 23:20:15,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:15,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:15,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:16,175 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:16,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:16,407 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:16,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:16,623 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:16,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:16,804 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:16,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:16,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:16,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,098 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,223 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,331 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,423 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,526 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,610 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,684 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,757 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:17,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:17,812 INFO L134 CoverageAnalysis]: Checked inductivity of 444 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-09 23:20:17,812 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:17,812 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1305281454] [2024-11-09 23:20:17,813 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1305281454] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:20:17,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [585896853] [2024-11-09 23:20:17,813 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 23:20:17,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:17,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:17,815 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) [2024-11-09 23:20:17,817 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 23:20:17,921 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 23:20:17,921 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 23:20:17,923 INFO L255 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-11-09 23:20:17,926 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:20:18,965 INFO L134 CoverageAnalysis]: Checked inductivity of 444 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2024-11-09 23:20:18,966 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 23:20:41,048 INFO L134 CoverageAnalysis]: Checked inductivity of 444 backedges. 0 proven. 366 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2024-11-09 23:20:41,049 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [585896853] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 23:20:41,049 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 23:20:41,049 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 30, 42] total 75 [2024-11-09 23:20:41,049 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [295491598] [2024-11-09 23:20:41,049 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 23:20:41,050 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 75 states [2024-11-09 23:20:41,050 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:41,052 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2024-11-09 23:20:41,055 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=549, Invalid=5001, Unknown=0, NotChecked=0, Total=5550 [2024-11-09 23:20:41,055 INFO L87 Difference]: Start difference. First operand 50 states and 51 transitions. Second operand has 75 states, 75 states have (on average 1.2666666666666666) internal successors, (95), 47 states have internal predecessors, (95), 15 states have call successors, (15), 1 states have call predecessors, (15), 27 states have return successors, (39), 28 states have call predecessors, (39), 15 states have call successors, (39) [2024-11-09 23:20:42,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:42,711 INFO L93 Difference]: Finished difference Result 93 states and 105 transitions. [2024-11-09 23:20:42,711 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2024-11-09 23:20:42,712 INFO L78 Accepts]: Start accepts. Automaton has has 75 states, 75 states have (on average 1.2666666666666666) internal successors, (95), 47 states have internal predecessors, (95), 15 states have call successors, (15), 1 states have call predecessors, (15), 27 states have return successors, (39), 28 states have call predecessors, (39), 15 states have call successors, (39) Word has length 84 [2024-11-09 23:20:42,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:42,715 INFO L225 Difference]: With dead ends: 93 [2024-11-09 23:20:42,717 INFO L226 Difference]: Without dead ends: 86 [2024-11-09 23:20:42,720 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 147 SyntacticMatches, 1 SemanticMatches, 119 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2863 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=1810, Invalid=12710, Unknown=0, NotChecked=0, Total=14520 [2024-11-09 23:20:42,724 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 206 mSDsluCounter, 694 mSDsCounter, 0 mSdLazyCounter, 1169 mSolverCounterSat, 84 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 231 SdHoareTripleChecker+Valid, 716 SdHoareTripleChecker+Invalid, 1253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 84 IncrementalHoareTripleChecker+Valid, 1169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:42,724 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [231 Valid, 716 Invalid, 1253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [84 Valid, 1169 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 23:20:42,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-09 23:20:42,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2024-11-09 23:20:42,746 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 58 states have (on average 1.0172413793103448) internal successors, (59), 59 states have internal predecessors, (59), 2 states have call successors, (2), 1 states have call predecessors, (2), 25 states have return successors, (26), 25 states have call predecessors, (26), 2 states have call successors, (26) [2024-11-09 23:20:42,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 87 transitions. [2024-11-09 23:20:42,747 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 87 transitions. Word has length 84 [2024-11-09 23:20:42,747 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:42,747 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 87 transitions. [2024-11-09 23:20:42,747 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 75 states, 75 states have (on average 1.2666666666666666) internal successors, (95), 47 states have internal predecessors, (95), 15 states have call successors, (15), 1 states have call predecessors, (15), 27 states have return successors, (39), 28 states have call predecessors, (39), 15 states have call successors, (39) [2024-11-09 23:20:42,747 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 87 transitions. [2024-11-09 23:20:42,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2024-11-09 23:20:42,752 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 23:20:42,752 INFO L215 NwaCegarLoop]: trace histogram [25, 25, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 23:20:42,769 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-09 23:20:42,952 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:42,953 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 23:20:42,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 23:20:42,953 INFO L85 PathProgramCache]: Analyzing trace with hash -1217314570, now seen corresponding path program 5 times [2024-11-09 23:20:42,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 23:20:42,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [406727251] [2024-11-09 23:20:42,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 23:20:42,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 23:20:43,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:43,735 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-09 23:20:43,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:44,444 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:44,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:45,046 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:45,072 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:45,634 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:45,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:46,116 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:46,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:46,620 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:46,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:47,065 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:47,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:47,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:47,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:47,790 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:47,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:48,105 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:48,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:48,433 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:48,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:48,797 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:48,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:49,082 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:49,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:49,312 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:49,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:49,511 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:49,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:49,691 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:49,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:49,855 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:49,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,141 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,276 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,525 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,624 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,738 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,865 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 23:20:50,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 23:20:50,925 INFO L134 CoverageAnalysis]: Checked inductivity of 1752 backedges. 0 proven. 876 refuted. 0 times theorem prover too weak. 876 trivial. 0 not checked. [2024-11-09 23:20:50,925 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 23:20:50,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [406727251] [2024-11-09 23:20:50,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [406727251] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 23:20:50,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2037165912] [2024-11-09 23:20:50,925 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-09 23:20:50,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:50,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 23:20:50,928 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) [2024-11-09 23:20:50,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 23:20:51,232 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 25 check-sat command(s) [2024-11-09 23:20:51,232 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 23:20:51,233 INFO L255 TraceCheckSpWp]: Trace formula consists of 381 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-09 23:20:51,237 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 23:20:53,923 INFO L134 CoverageAnalysis]: Checked inductivity of 1752 backedges. 876 proven. 0 refuted. 0 times theorem prover too weak. 876 trivial. 0 not checked. [2024-11-09 23:20:53,924 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 23:20:53,924 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2037165912] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 23:20:53,924 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 23:20:53,924 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [54] imperfect sequences [54] total 106 [2024-11-09 23:20:53,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [280510770] [2024-11-09 23:20:53,924 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 23:20:53,925 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 54 states [2024-11-09 23:20:53,925 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 23:20:53,926 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2024-11-09 23:20:53,928 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=789, Invalid=10341, Unknown=0, NotChecked=0, Total=11130 [2024-11-09 23:20:53,929 INFO L87 Difference]: Start difference. First operand 86 states and 87 transitions. Second operand has 54 states, 53 states have (on average 1.1132075471698113) internal successors, (59), 29 states have internal predecessors, (59), 2 states have call successors, (2), 1 states have call predecessors, (2), 25 states have return successors, (25), 25 states have call predecessors, (25), 2 states have call successors, (25) [2024-11-09 23:20:54,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 23:20:54,125 INFO L93 Difference]: Finished difference Result 86 states and 87 transitions. [2024-11-09 23:20:54,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2024-11-09 23:20:54,125 INFO L78 Accepts]: Start accepts. Automaton has has 54 states, 53 states have (on average 1.1132075471698113) internal successors, (59), 29 states have internal predecessors, (59), 2 states have call successors, (2), 1 states have call predecessors, (2), 25 states have return successors, (25), 25 states have call predecessors, (25), 2 states have call successors, (25) Word has length 156 [2024-11-09 23:20:54,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 23:20:54,126 INFO L225 Difference]: With dead ends: 86 [2024-11-09 23:20:54,126 INFO L226 Difference]: Without dead ends: 0 [2024-11-09 23:20:54,130 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 258 GetRequests, 153 SyntacticMatches, 1 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 745 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=789, Invalid=10341, Unknown=0, NotChecked=0, Total=11130 [2024-11-09 23:20:54,131 INFO L432 NwaCegarLoop]: 59 mSDtfsCounter, 0 mSDsluCounter, 567 mSDsCounter, 0 mSdLazyCounter, 399 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 626 SdHoareTripleChecker+Invalid, 399 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 399 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 23:20:54,131 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 626 Invalid, 399 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 399 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 23:20:54,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-09 23:20:54,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-09 23:20:54,132 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) [2024-11-09 23:20:54,132 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-09 23:20:54,133 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 156 [2024-11-09 23:20:54,133 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 23:20:54,133 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 23:20:54,133 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 54 states, 53 states have (on average 1.1132075471698113) internal successors, (59), 29 states have internal predecessors, (59), 2 states have call successors, (2), 1 states have call predecessors, (2), 25 states have return successors, (25), 25 states have call predecessors, (25), 2 states have call successors, (25) [2024-11-09 23:20:54,133 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-09 23:20:54,133 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-09 23:20:54,136 INFO L782 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-09 23:20:54,152 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 23:20:54,337 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 23:20:54,340 INFO L407 BasicCegarLoop]: Path program histogram: [5, 1] [2024-11-09 23:20:54,342 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-09 23:20:54,735 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-09 23:20:54,773 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.11 11:20:54 BoogieIcfgContainer [2024-11-09 23:20:54,773 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-09 23:20:54,773 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 23:20:54,773 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 23:20:54,773 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 23:20:54,774 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 11:20:05" (3/4) ... [2024-11-09 23:20:54,776 INFO L143 WitnessPrinter]: Generating witness for correct program [2024-11-09 23:20:54,780 INFO L393 IcfgBacktranslator]: Ignoring RootEdge to procedure hanoi [2024-11-09 23:20:54,783 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 12 nodes and edges [2024-11-09 23:20:54,784 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-11-09 23:20:54,784 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-09 23:20:54,784 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-09 23:20:54,866 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-09 23:20:54,867 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-09 23:20:54,867 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 23:20:54,868 INFO L158 Benchmark]: Toolchain (without parser) took 49785.41ms. Allocated memory was 161.5MB in the beginning and 759.2MB in the end (delta: 597.7MB). Free memory was 98.3MB in the beginning and 666.7MB in the end (delta: -568.4MB). Peak memory consumption was 29.8MB. Max. memory is 16.1GB. [2024-11-09 23:20:54,868 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 96.5MB. Free memory is still 51.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 23:20:54,868 INFO L158 Benchmark]: CACSL2BoogieTranslator took 267.18ms. Allocated memory is still 161.5MB. Free memory was 98.3MB in the beginning and 130.8MB in the end (delta: -32.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 23:20:54,868 INFO L158 Benchmark]: Boogie Procedure Inliner took 28.07ms. Allocated memory is still 161.5MB. Free memory was 130.8MB in the beginning and 129.5MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 23:20:54,869 INFO L158 Benchmark]: Boogie Preprocessor took 25.74ms. Allocated memory is still 161.5MB. Free memory was 129.5MB in the beginning and 128.1MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 23:20:54,870 INFO L158 Benchmark]: IcfgBuilder took 236.79ms. Allocated memory is still 161.5MB. Free memory was 127.4MB in the beginning and 117.0MB in the end (delta: 10.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-09 23:20:54,870 INFO L158 Benchmark]: TraceAbstraction took 49126.08ms. Allocated memory was 161.5MB in the beginning and 759.2MB in the end (delta: 597.7MB). Free memory was 116.3MB in the beginning and 670.9MB in the end (delta: -554.6MB). Peak memory consumption was 455.0MB. Max. memory is 16.1GB. [2024-11-09 23:20:54,870 INFO L158 Benchmark]: Witness Printer took 93.83ms. Allocated memory is still 759.2MB. Free memory was 670.9MB in the beginning and 666.7MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-09 23:20:54,872 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18ms. Allocated memory is still 96.5MB. Free memory is still 51.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 267.18ms. Allocated memory is still 161.5MB. Free memory was 98.3MB in the beginning and 130.8MB in the end (delta: -32.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 28.07ms. Allocated memory is still 161.5MB. Free memory was 130.8MB in the beginning and 129.5MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 25.74ms. Allocated memory is still 161.5MB. Free memory was 129.5MB in the beginning and 128.1MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 236.79ms. Allocated memory is still 161.5MB. Free memory was 127.4MB in the beginning and 117.0MB in the end (delta: 10.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 49126.08ms. Allocated memory was 161.5MB in the beginning and 759.2MB in the end (delta: 597.7MB). Free memory was 116.3MB in the beginning and 670.9MB in the end (delta: -554.6MB). Peak memory consumption was 455.0MB. Max. memory is 16.1GB. * Witness Printer took 93.83ms. Allocated memory is still 759.2MB. Free memory was 670.9MB in the beginning and 666.7MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. 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: 35]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 19 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 48.6s, OverallIterations: 6, TraceHistogramMax: 25, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 3.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 364 SdHoareTripleChecker+Valid, 1.3s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 313 mSDsluCounter, 1964 SdHoareTripleChecker+Invalid, 1.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1828 mSDsCounter, 120 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2424 IncrementalHoareTripleChecker+Invalid, 2544 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 120 mSolverCounterUnsat, 136 mSDtfsCounter, 2424 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 815 GetRequests, 458 SyntacticMatches, 5 SemanticMatches, 352 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4714 ImplicationChecksByTransitivity, 9.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=86occurred in iteration=5, InterpolantAutomatonStates: 174, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 43.5s InterpolantComputationTime, 684 NumberOfCodeBlocks, 684 NumberOfCodeBlocksAsserted, 43 NumberOfCheckSat, 849 ConstructedInterpolants, 0 QuantifiedInterpolants, 3467 SizeOfPredicates, 22 NumberOfNonLiveVariables, 869 ConjunctsInSsa, 169 ConjunctsInUnsatCore, 15 InterpolantComputations, 2 PerfectInterpolantSequences, 3326/5280 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 - ProcedureContractResult [Line: 18]: Procedure Contract for hanoi Derived contract for procedure hanoi. Ensures: ((((((((((((((((n <= 13) && (8191 <= \result)) || ((3 <= \result) && (n <= 2))) || ((n <= 11) && (2047 <= \result))) || ((n <= 6) && (63 <= \result))) || ((511 <= \result) && (n <= 9))) || ((n <= 7) && (127 <= \result))) || (33554430 < \result)) || ((n <= 8) && (255 <= \result))) || ((n <= 12) && (4095 <= \result))) || ((\result == 1) && (n == 1))) || ((n <= 5) && (31 <= \result))) || ((1023 <= \result) && (n <= 10))) || ((7 <= \result) && (n <= 3))) || ((16383 <= \result) && (((long long) 8178 + n) <= \result))) || ((15 <= \result) && (n <= 4))) RESULT: Ultimate proved your program to be correct! [2024-11-09 23:20:54,908 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (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