./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive/Fibonacci03.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8fc3dc66 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/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.6.800.v20240513-1750.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/Fibonacci03.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 be0a584ba9648c80e7a0523ff51ba530f1926c55cecd3c62f2cee05fbbff42e3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-16 18:50:57,014 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-16 18:50:57,056 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-16 18:50:57,059 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-16 18:50:57,059 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-16 18:50:57,077 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-16 18:50:57,078 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-16 18:50:57,078 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-16 18:50:57,078 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-16 18:50:57,078 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-16 18:50:57,079 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-16 18:50:57,079 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * Use SBE=true [2025-03-16 18:50:57,079 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-16 18:50:57,079 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-16 18:50:57,080 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-16 18:50:57,080 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:50:57,081 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-16 18:50:57,081 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-16 18:50:57,082 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-16 18:50:57,082 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 -> be0a584ba9648c80e7a0523ff51ba530f1926c55cecd3c62f2cee05fbbff42e3 [2025-03-16 18:50:57,326 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-16 18:50:57,335 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-16 18:50:57,337 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-16 18:50:57,337 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-16 18:50:57,338 INFO L274 PluginConnector]: CDTParser initialized [2025-03-16 18:50:57,339 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci03.c [2025-03-16 18:50:58,505 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e130c4d87/c034dba2249a4c76812b6de4bf549539/FLAG3b4a2eb33 [2025-03-16 18:50:58,767 INFO L384 CDTParser]: Found 1 translation units. [2025-03-16 18:50:58,768 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci03.c [2025-03-16 18:50:58,773 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e130c4d87/c034dba2249a4c76812b6de4bf549539/FLAG3b4a2eb33 [2025-03-16 18:50:59,091 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e130c4d87/c034dba2249a4c76812b6de4bf549539 [2025-03-16 18:50:59,093 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-16 18:50:59,095 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-16 18:50:59,096 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-16 18:50:59,097 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-16 18:50:59,101 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-16 18:50:59,102 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,102 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@35f16c2c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59, skipping insertion in model container [2025-03-16 18:50:59,104 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,114 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-16 18:50:59,219 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/Fibonacci03.c[788,801] [2025-03-16 18:50:59,222 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:50:59,228 INFO L200 MainTranslator]: Completed pre-run [2025-03-16 18:50:59,239 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/Fibonacci03.c[788,801] [2025-03-16 18:50:59,240 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-16 18:50:59,250 INFO L204 MainTranslator]: Completed translation [2025-03-16 18:50:59,251 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59 WrapperNode [2025-03-16 18:50:59,251 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-16 18:50:59,252 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-16 18:50:59,253 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-16 18:50:59,253 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-16 18:50:59,258 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,263 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,273 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 26 [2025-03-16 18:50:59,273 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-16 18:50:59,273 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-16 18:50:59,273 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-16 18:50:59,273 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-16 18:50:59,279 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,279 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,281 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,292 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]. [2025-03-16 18:50:59,292 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,293 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,295 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,298 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,299 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,299 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,300 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-16 18:50:59,300 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-16 18:50:59,300 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-16 18:50:59,300 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-16 18:50:59,301 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (1/1) ... [2025-03-16 18:50:59,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-16 18:50:59,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:50:59,327 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) [2025-03-16 18:50:59,332 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 [2025-03-16 18:50:59,346 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2025-03-16 18:50:59,346 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2025-03-16 18:50:59,346 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-16 18:50:59,346 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-16 18:50:59,346 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-16 18:50:59,346 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-16 18:50:59,392 INFO L256 CfgBuilder]: Building ICFG [2025-03-16 18:50:59,393 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-16 18:50:59,456 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L22: havoc #t~ret4;havoc #t~ret5; [2025-03-16 18:50:59,494 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2025-03-16 18:50:59,495 INFO L307 CfgBuilder]: Performing block encoding [2025-03-16 18:50:59,502 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-16 18:50:59,502 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-16 18:50:59,503 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:50:59 BoogieIcfgContainer [2025-03-16 18:50:59,503 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-16 18:50:59,506 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-16 18:50:59,506 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-16 18:50:59,509 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-16 18:50:59,510 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.03 06:50:59" (1/3) ... [2025-03-16 18:50:59,510 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b88072f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:50:59, skipping insertion in model container [2025-03-16 18:50:59,511 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.03 06:50:59" (2/3) ... [2025-03-16 18:50:59,511 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b88072f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.03 06:50:59, skipping insertion in model container [2025-03-16 18:50:59,511 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.03 06:50:59" (3/3) ... [2025-03-16 18:50:59,512 INFO L128 eAbstractionObserver]: Analyzing ICFG Fibonacci03.c [2025-03-16 18:50:59,523 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-16 18:50:59,524 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG Fibonacci03.c that has 2 procedures, 19 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-16 18:50:59,557 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-16 18:50:59,565 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;@3ce3bf96, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-16 18:50:59,565 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-16 18:50:59,570 INFO L276 IsEmpty]: Start isEmpty. Operand has 19 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-16 18:50:59,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-16 18:50:59,576 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:59,576 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:59,576 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:59,580 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:59,580 INFO L85 PathProgramCache]: Analyzing trace with hash -165355574, now seen corresponding path program 1 times [2025-03-16 18:50:59,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:59,588 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [359775729] [2025-03-16 18:50:59,588 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:59,589 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:59,631 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-16 18:50:59,649 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-16 18:50:59,650 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:59,650 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:59,774 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 18:50:59,775 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:59,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [359775729] [2025-03-16 18:50:59,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [359775729] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:50:59,777 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:50:59,778 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:50:59,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [428609474] [2025-03-16 18:50:59,779 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:50:59,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:50:59,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:59,796 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:50:59,796 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:50:59,798 INFO L87 Difference]: Start difference. First operand has 19 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 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) [2025-03-16 18:50:59,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:50:59,872 INFO L93 Difference]: Finished difference Result 30 states and 39 transitions. [2025-03-16 18:50:59,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:50:59,874 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 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 10 [2025-03-16 18:50:59,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:50:59,879 INFO L225 Difference]: With dead ends: 30 [2025-03-16 18:50:59,879 INFO L226 Difference]: Without dead ends: 20 [2025-03-16 18:50:59,881 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:50:59,883 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 5 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 47 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:50:59,883 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 47 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:50:59,892 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-16 18:50:59,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 18. [2025-03-16 18:50:59,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 13 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-16 18:50:59,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2025-03-16 18:50:59,907 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 10 [2025-03-16 18:50:59,907 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:50:59,908 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2025-03-16 18:50:59,908 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 5 states have internal predecessors, (8), 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) [2025-03-16 18:50:59,908 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2025-03-16 18:50:59,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-16 18:50:59,909 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:50:59,909 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:50:59,909 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-16 18:50:59,909 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:50:59,910 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:50:59,910 INFO L85 PathProgramCache]: Analyzing trace with hash 1699155895, now seen corresponding path program 1 times [2025-03-16 18:50:59,910 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:50:59,910 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1693699519] [2025-03-16 18:50:59,910 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:50:59,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:50:59,914 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-16 18:50:59,918 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-16 18:50:59,918 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:50:59,918 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:50:59,965 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-16 18:50:59,965 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:50:59,965 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1693699519] [2025-03-16 18:50:59,965 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1693699519] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-16 18:50:59,965 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-16 18:50:59,965 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-16 18:50:59,965 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539315371] [2025-03-16 18:50:59,966 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-16 18:50:59,966 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-16 18:50:59,966 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:50:59,967 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-16 18:50:59,967 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:50:59,967 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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) [2025-03-16 18:51:00,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:00,018 INFO L93 Difference]: Finished difference Result 24 states and 29 transitions. [2025-03-16 18:51:00,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-16 18:51:00,019 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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 11 [2025-03-16 18:51:00,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:00,020 INFO L225 Difference]: With dead ends: 24 [2025-03-16 18:51:00,020 INFO L226 Difference]: Without dead ends: 20 [2025-03-16 18:51:00,020 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-16 18:51:00,020 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 4 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:00,021 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 35 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-16 18:51:00,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-16 18:51:00,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 18. [2025-03-16 18:51:00,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 13 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-16 18:51:00,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2025-03-16 18:51:00,025 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 11 [2025-03-16 18:51:00,025 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:00,025 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2025-03-16 18:51:00,025 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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) [2025-03-16 18:51:00,025 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2025-03-16 18:51:00,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-16 18:51:00,026 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:00,026 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:00,026 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-16 18:51:00,026 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:00,026 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:00,027 INFO L85 PathProgramCache]: Analyzing trace with hash -1017906903, now seen corresponding path program 1 times [2025-03-16 18:51:00,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:00,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [716194704] [2025-03-16 18:51:00,027 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:51:00,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:00,033 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-16 18:51:00,043 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 18:51:00,043 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:00,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,143 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 18:51:00,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:00,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [716194704] [2025-03-16 18:51:00,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [716194704] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:00,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1732181689] [2025-03-16 18:51:00,144 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:51:00,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:00,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:00,146 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) [2025-03-16 18:51:00,148 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-16 18:51:00,174 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-16 18:51:00,191 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-16 18:51:00,191 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:00,192 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,195 INFO L256 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-16 18:51:00,197 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:00,261 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-16 18:51:00,261 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:00,460 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-16 18:51:00,460 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1732181689] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:00,460 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:00,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 12 [2025-03-16 18:51:00,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [635501478] [2025-03-16 18:51:00,461 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:00,461 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 18:51:00,461 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:00,461 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 18:51:00,462 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2025-03-16 18:51:00,462 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 12 states, 11 states have (on average 3.0) internal successors, (33), 12 states have internal predecessors, (33), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2025-03-16 18:51:00,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:00,578 INFO L93 Difference]: Finished difference Result 42 states and 60 transitions. [2025-03-16 18:51:00,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:51:00,579 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.0) internal successors, (33), 12 states have internal predecessors, (33), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) Word has length 23 [2025-03-16 18:51:00,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:00,579 INFO L225 Difference]: With dead ends: 42 [2025-03-16 18:51:00,579 INFO L226 Difference]: Without dead ends: 25 [2025-03-16 18:51:00,580 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 42 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=151, Unknown=0, NotChecked=0, Total=210 [2025-03-16 18:51:00,580 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 24 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:00,580 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 46 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:00,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-03-16 18:51:00,584 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2025-03-16 18:51:00,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.125) internal successors, (18), 18 states have internal predecessors, (18), 4 states have call successors, (4), 1 states have call predecessors, (4), 4 states have return successors, (12), 5 states have call predecessors, (12), 4 states have call successors, (12) [2025-03-16 18:51:00,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 34 transitions. [2025-03-16 18:51:00,585 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 34 transitions. Word has length 23 [2025-03-16 18:51:00,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:00,586 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 34 transitions. [2025-03-16 18:51:00,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.0) internal successors, (33), 12 states have internal predecessors, (33), 7 states have call successors, (7), 1 states have call predecessors, (7), 5 states have return successors, (9), 5 states have call predecessors, (9), 7 states have call successors, (9) [2025-03-16 18:51:00,587 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 34 transitions. [2025-03-16 18:51:00,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2025-03-16 18:51:00,589 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:00,589 INFO L218 NwaCegarLoop]: trace histogram [9, 9, 6, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:00,596 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-16 18:51:00,793 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:00,793 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:00,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:00,794 INFO L85 PathProgramCache]: Analyzing trace with hash 1644795852, now seen corresponding path program 1 times [2025-03-16 18:51:00,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:00,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1997219106] [2025-03-16 18:51:00,794 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:51:00,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:00,800 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-16 18:51:00,814 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-16 18:51:00,814 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:00,814 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,931 INFO L134 CoverageAnalysis]: Checked inductivity of 183 backedges. 16 proven. 72 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2025-03-16 18:51:00,931 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:00,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1997219106] [2025-03-16 18:51:00,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1997219106] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:00,932 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1756991865] [2025-03-16 18:51:00,932 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-16 18:51:00,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:00,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:00,933 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) [2025-03-16 18:51:00,935 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-16 18:51:00,963 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 64 statements into 1 equivalence classes. [2025-03-16 18:51:00,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 64 of 64 statements. [2025-03-16 18:51:00,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:00,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:00,981 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 18:51:00,983 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:01,027 INFO L134 CoverageAnalysis]: Checked inductivity of 183 backedges. 16 proven. 72 refuted. 0 times theorem prover too weak. 95 trivial. 0 not checked. [2025-03-16 18:51:01,027 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:01,430 INFO L134 CoverageAnalysis]: Checked inductivity of 183 backedges. 16 proven. 79 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2025-03-16 18:51:01,430 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1756991865] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:01,430 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:01,430 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 9] total 12 [2025-03-16 18:51:01,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1164021564] [2025-03-16 18:51:01,430 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:01,431 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-03-16 18:51:01,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:01,431 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-03-16 18:51:01,431 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2025-03-16 18:51:01,432 INFO L87 Difference]: Start difference. First operand 25 states and 34 transitions. Second operand has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2025-03-16 18:51:01,563 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:01,565 INFO L93 Difference]: Finished difference Result 44 states and 74 transitions. [2025-03-16 18:51:01,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-16 18:51:01,565 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) Word has length 64 [2025-03-16 18:51:01,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:01,567 INFO L225 Difference]: With dead ends: 44 [2025-03-16 18:51:01,567 INFO L226 Difference]: Without dead ends: 38 [2025-03-16 18:51:01,567 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 123 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=145, Unknown=0, NotChecked=0, Total=210 [2025-03-16 18:51:01,568 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 21 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:01,568 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 67 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:01,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2025-03-16 18:51:01,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 35. [2025-03-16 18:51:01,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.0909090909090908) internal successors, (24), 24 states have internal predecessors, (24), 6 states have call successors, (6), 1 states have call predecessors, (6), 6 states have return successors, (30), 9 states have call predecessors, (30), 6 states have call successors, (30) [2025-03-16 18:51:01,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 60 transitions. [2025-03-16 18:51:01,581 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 60 transitions. Word has length 64 [2025-03-16 18:51:01,582 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:01,582 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 60 transitions. [2025-03-16 18:51:01,582 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.1666666666666665) internal successors, (38), 12 states have internal predecessors, (38), 7 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2025-03-16 18:51:01,582 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 60 transitions. [2025-03-16 18:51:01,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2025-03-16 18:51:01,586 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:01,586 INFO L218 NwaCegarLoop]: trace histogram [19, 19, 13, 9, 9, 9, 9, 9, 9, 9, 6, 4, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:01,592 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:01,786 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,SelfDestructingSolverStorable3 [2025-03-16 18:51:01,787 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:01,787 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:01,787 INFO L85 PathProgramCache]: Analyzing trace with hash -834550159, now seen corresponding path program 2 times [2025-03-16 18:51:01,787 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:01,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1124994849] [2025-03-16 18:51:01,787 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:01,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:01,795 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 131 statements into 2 equivalence classes. [2025-03-16 18:51:01,813 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 131 of 131 statements. [2025-03-16 18:51:01,813 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:01,813 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:02,023 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 52 proven. 316 refuted. 0 times theorem prover too weak. 538 trivial. 0 not checked. [2025-03-16 18:51:02,024 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:02,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1124994849] [2025-03-16 18:51:02,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1124994849] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:02,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087473495] [2025-03-16 18:51:02,024 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:02,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:02,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:02,027 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) [2025-03-16 18:51:02,030 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-16 18:51:02,064 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 131 statements into 2 equivalence classes. [2025-03-16 18:51:02,102 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 131 of 131 statements. [2025-03-16 18:51:02,102 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:02,102 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:02,106 INFO L256 TraceCheckSpWp]: Trace formula consists of 312 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-16 18:51:02,110 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:02,171 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 52 proven. 316 refuted. 0 times theorem prover too weak. 538 trivial. 0 not checked. [2025-03-16 18:51:02,171 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:02,952 INFO L134 CoverageAnalysis]: Checked inductivity of 906 backedges. 52 proven. 342 refuted. 0 times theorem prover too weak. 512 trivial. 0 not checked. [2025-03-16 18:51:02,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087473495] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:02,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:02,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 13] total 16 [2025-03-16 18:51:02,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129244972] [2025-03-16 18:51:02,953 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:02,954 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-03-16 18:51:02,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:02,954 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-03-16 18:51:02,954 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=174, Unknown=0, NotChecked=0, Total=240 [2025-03-16 18:51:02,955 INFO L87 Difference]: Start difference. First operand 35 states and 60 transitions. Second operand has 16 states, 16 states have (on average 3.125) internal successors, (50), 16 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (17), 8 states have call predecessors, (17), 11 states have call successors, (17) [2025-03-16 18:51:03,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:03,086 INFO L93 Difference]: Finished difference Result 54 states and 110 transitions. [2025-03-16 18:51:03,087 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-16 18:51:03,087 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.125) internal successors, (50), 16 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (17), 8 states have call predecessors, (17), 11 states have call successors, (17) Word has length 131 [2025-03-16 18:51:03,087 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:03,089 INFO L225 Difference]: With dead ends: 54 [2025-03-16 18:51:03,089 INFO L226 Difference]: Without dead ends: 48 [2025-03-16 18:51:03,089 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 278 GetRequests, 255 SyntacticMatches, 4 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=131, Invalid=289, Unknown=0, NotChecked=0, Total=420 [2025-03-16 18:51:03,089 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 33 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 66 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 142 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 66 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:03,090 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 71 Invalid, 142 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [66 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:03,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2025-03-16 18:51:03,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 45. [2025-03-16 18:51:03,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.0714285714285714) internal successors, (30), 30 states have internal predecessors, (30), 8 states have call successors, (8), 1 states have call predecessors, (8), 8 states have return successors, (56), 13 states have call predecessors, (56), 8 states have call successors, (56) [2025-03-16 18:51:03,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 94 transitions. [2025-03-16 18:51:03,107 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 94 transitions. Word has length 131 [2025-03-16 18:51:03,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:03,107 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 94 transitions. [2025-03-16 18:51:03,107 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.125) internal successors, (50), 16 states have internal predecessors, (50), 11 states have call successors, (13), 1 states have call predecessors, (13), 7 states have return successors, (17), 8 states have call predecessors, (17), 11 states have call successors, (17) [2025-03-16 18:51:03,107 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 94 transitions. [2025-03-16 18:51:03,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 398 [2025-03-16 18:51:03,112 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:03,112 INFO L218 NwaCegarLoop]: trace histogram [59, 59, 39, 29, 29, 29, 29, 29, 29, 29, 20, 10, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:03,120 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:03,312 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:03,313 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:03,313 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:03,313 INFO L85 PathProgramCache]: Analyzing trace with hash 2138179955, now seen corresponding path program 3 times [2025-03-16 18:51:03,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:03,313 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [758513469] [2025-03-16 18:51:03,314 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:51:03,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:03,325 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 397 statements into 46 equivalence classes. [2025-03-16 18:51:03,334 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 50 of 397 statements. [2025-03-16 18:51:03,334 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-16 18:51:03,334 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:03,433 INFO L134 CoverageAnalysis]: Checked inductivity of 9209 backedges. 1062 proven. 7 refuted. 0 times theorem prover too weak. 8140 trivial. 0 not checked. [2025-03-16 18:51:03,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:03,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [758513469] [2025-03-16 18:51:03,434 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [758513469] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:03,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [604195305] [2025-03-16 18:51:03,434 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-16 18:51:03,434 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:03,434 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:03,436 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) [2025-03-16 18:51:03,437 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-16 18:51:03,491 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 397 statements into 46 equivalence classes. [2025-03-16 18:51:03,503 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 50 of 397 statements. [2025-03-16 18:51:03,504 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-16 18:51:03,504 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:03,505 INFO L256 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-16 18:51:03,510 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:03,560 INFO L134 CoverageAnalysis]: Checked inductivity of 9209 backedges. 1252 proven. 12 refuted. 0 times theorem prover too weak. 7945 trivial. 0 not checked. [2025-03-16 18:51:03,560 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:04,522 INFO L134 CoverageAnalysis]: Checked inductivity of 9209 backedges. 1252 proven. 14 refuted. 0 times theorem prover too weak. 7943 trivial. 0 not checked. [2025-03-16 18:51:04,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [604195305] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:04,523 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:04,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 15 [2025-03-16 18:51:04,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [7732333] [2025-03-16 18:51:04,523 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:04,524 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-16 18:51:04,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:04,524 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-16 18:51:04,524 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2025-03-16 18:51:04,525 INFO L87 Difference]: Start difference. First operand 45 states and 94 transitions. Second operand has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 6 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 5 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-16 18:51:04,609 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:04,609 INFO L93 Difference]: Finished difference Result 92 states and 239 transitions. [2025-03-16 18:51:04,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-16 18:51:04,610 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 6 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 5 states have call predecessors, (11), 6 states have call successors, (11) Word has length 397 [2025-03-16 18:51:04,610 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:04,611 INFO L225 Difference]: With dead ends: 92 [2025-03-16 18:51:04,611 INFO L226 Difference]: Without dead ends: 50 [2025-03-16 18:51:04,612 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 804 GetRequests, 784 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=96, Invalid=210, Unknown=0, NotChecked=0, Total=306 [2025-03-16 18:51:04,615 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 17 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:04,615 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 62 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:04,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-03-16 18:51:04,624 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 47. [2025-03-16 18:51:04,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 8 states have call successors, (8), 2 states have call predecessors, (8), 8 states have return successors, (51), 13 states have call predecessors, (51), 8 states have call successors, (51) [2025-03-16 18:51:04,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 91 transitions. [2025-03-16 18:51:04,629 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 91 transitions. Word has length 397 [2025-03-16 18:51:04,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:04,629 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 91 transitions. [2025-03-16 18:51:04,629 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.7333333333333334) internal successors, (41), 15 states have internal predecessors, (41), 6 states have call successors, (9), 1 states have call predecessors, (9), 5 states have return successors, (11), 5 states have call predecessors, (11), 6 states have call successors, (11) [2025-03-16 18:51:04,629 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 91 transitions. [2025-03-16 18:51:04,645 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 574 [2025-03-16 18:51:04,645 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:04,646 INFO L218 NwaCegarLoop]: trace histogram [83, 83, 71, 41, 41, 41, 41, 41, 41, 41, 30, 12, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:04,652 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-16 18:51:04,846 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:04,847 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:04,847 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:04,847 INFO L85 PathProgramCache]: Analyzing trace with hash -931192141, now seen corresponding path program 4 times [2025-03-16 18:51:04,848 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:04,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [943354415] [2025-03-16 18:51:04,848 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:51:04,848 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:04,861 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 573 statements into 2 equivalence classes. [2025-03-16 18:51:04,913 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 487 of 573 statements. [2025-03-16 18:51:04,916 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:51:04,916 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:05,509 INFO L134 CoverageAnalysis]: Checked inductivity of 19377 backedges. 679 proven. 2647 refuted. 0 times theorem prover too weak. 16051 trivial. 0 not checked. [2025-03-16 18:51:05,509 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:05,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [943354415] [2025-03-16 18:51:05,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [943354415] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:05,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [852750520] [2025-03-16 18:51:05,509 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-16 18:51:05,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:05,510 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:05,511 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) [2025-03-16 18:51:05,515 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-16 18:51:05,594 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 573 statements into 2 equivalence classes. [2025-03-16 18:51:05,689 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 487 of 573 statements. [2025-03-16 18:51:05,690 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-16 18:51:05,690 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:05,692 INFO L256 TraceCheckSpWp]: Trace formula consists of 1018 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-16 18:51:05,706 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:05,820 INFO L134 CoverageAnalysis]: Checked inductivity of 19377 backedges. 5662 proven. 170 refuted. 0 times theorem prover too weak. 13545 trivial. 0 not checked. [2025-03-16 18:51:05,820 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:07,716 INFO L134 CoverageAnalysis]: Checked inductivity of 19377 backedges. 578 proven. 2992 refuted. 0 times theorem prover too weak. 15807 trivial. 0 not checked. [2025-03-16 18:51:07,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [852750520] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:07,716 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:07,716 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11, 15] total 23 [2025-03-16 18:51:07,717 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [766264779] [2025-03-16 18:51:07,717 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:07,717 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-03-16 18:51:07,720 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:07,720 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-03-16 18:51:07,720 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=414, Unknown=0, NotChecked=0, Total=506 [2025-03-16 18:51:07,721 INFO L87 Difference]: Start difference. First operand 47 states and 91 transitions. Second operand has 23 states, 23 states have (on average 3.260869565217391) internal successors, (75), 23 states have internal predecessors, (75), 17 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (31), 13 states have call predecessors, (31), 17 states have call successors, (31) [2025-03-16 18:51:07,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:07,984 INFO L93 Difference]: Finished difference Result 110 states and 240 transitions. [2025-03-16 18:51:07,984 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2025-03-16 18:51:07,984 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 3.260869565217391) internal successors, (75), 23 states have internal predecessors, (75), 17 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (31), 13 states have call predecessors, (31), 17 states have call successors, (31) Word has length 573 [2025-03-16 18:51:07,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:07,985 INFO L225 Difference]: With dead ends: 110 [2025-03-16 18:51:07,985 INFO L226 Difference]: Without dead ends: 66 [2025-03-16 18:51:07,987 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1177 GetRequests, 1133 SyntacticMatches, 7 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 315 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=384, Invalid=1098, Unknown=0, NotChecked=0, Total=1482 [2025-03-16 18:51:07,987 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 95 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 95 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 333 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:07,987 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [95 Valid, 127 Invalid, 333 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 223 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:07,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-03-16 18:51:07,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2025-03-16 18:51:07,992 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 44 states have internal predecessors, (51), 10 states have call successors, (10), 8 states have call predecessors, (10), 8 states have return successors, (28), 13 states have call predecessors, (28), 10 states have call successors, (28) [2025-03-16 18:51:07,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 89 transitions. [2025-03-16 18:51:07,993 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 89 transitions. Word has length 573 [2025-03-16 18:51:07,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:07,995 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 89 transitions. [2025-03-16 18:51:07,995 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 3.260869565217391) internal successors, (75), 23 states have internal predecessors, (75), 17 states have call successors, (24), 2 states have call predecessors, (24), 10 states have return successors, (31), 13 states have call predecessors, (31), 17 states have call successors, (31) [2025-03-16 18:51:07,995 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 89 transitions. [2025-03-16 18:51:07,996 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 406 [2025-03-16 18:51:07,996 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:07,996 INFO L218 NwaCegarLoop]: trace histogram [59, 59, 47, 29, 29, 29, 29, 29, 29, 29, 18, 12, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:08,003 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:08,200 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:08,200 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:08,200 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:08,200 INFO L85 PathProgramCache]: Analyzing trace with hash -2108131021, now seen corresponding path program 5 times [2025-03-16 18:51:08,200 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:08,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [815387761] [2025-03-16 18:51:08,200 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:51:08,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:08,210 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 405 statements into 50 equivalence classes. [2025-03-16 18:51:08,229 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) and asserted 161 of 405 statements. [2025-03-16 18:51:08,229 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2025-03-16 18:51:08,230 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:08,385 INFO L134 CoverageAnalysis]: Checked inductivity of 9549 backedges. 916 proven. 1216 refuted. 0 times theorem prover too weak. 7417 trivial. 0 not checked. [2025-03-16 18:51:08,385 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:08,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [815387761] [2025-03-16 18:51:08,385 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [815387761] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:08,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [211621101] [2025-03-16 18:51:08,386 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-16 18:51:08,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:08,386 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:08,388 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:51:08,389 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-03-16 18:51:08,462 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 405 statements into 50 equivalence classes. [2025-03-16 18:51:08,498 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) and asserted 161 of 405 statements. [2025-03-16 18:51:08,498 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 20 check-sat command(s) [2025-03-16 18:51:08,499 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:08,501 INFO L256 TraceCheckSpWp]: Trace formula consists of 363 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-16 18:51:08,507 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:08,557 INFO L134 CoverageAnalysis]: Checked inductivity of 9549 backedges. 5462 proven. 140 refuted. 0 times theorem prover too weak. 3947 trivial. 0 not checked. [2025-03-16 18:51:08,557 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:09,932 INFO L134 CoverageAnalysis]: Checked inductivity of 9549 backedges. 906 proven. 1238 refuted. 0 times theorem prover too weak. 7405 trivial. 0 not checked. [2025-03-16 18:51:09,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [211621101] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:09,933 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:09,933 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 15] total 18 [2025-03-16 18:51:09,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [80853896] [2025-03-16 18:51:09,933 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:09,934 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-16 18:51:09,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:09,934 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-16 18:51:09,934 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2025-03-16 18:51:09,935 INFO L87 Difference]: Start difference. First operand 66 states and 89 transitions. Second operand has 18 states, 18 states have (on average 3.611111111111111) internal successors, (65), 18 states have internal predecessors, (65), 14 states have call successors, (18), 2 states have call predecessors, (18), 8 states have return successors, (23), 7 states have call predecessors, (23), 14 states have call successors, (23) [2025-03-16 18:51:10,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:10,098 INFO L93 Difference]: Finished difference Result 132 states and 201 transitions. [2025-03-16 18:51:10,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-16 18:51:10,098 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.611111111111111) internal successors, (65), 18 states have internal predecessors, (65), 14 states have call successors, (18), 2 states have call predecessors, (18), 8 states have return successors, (23), 7 states have call predecessors, (23), 14 states have call successors, (23) Word has length 405 [2025-03-16 18:51:10,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:10,100 INFO L225 Difference]: With dead ends: 132 [2025-03-16 18:51:10,100 INFO L226 Difference]: Without dead ends: 70 [2025-03-16 18:51:10,100 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 832 GetRequests, 800 SyntacticMatches, 7 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=203, Invalid=499, Unknown=0, NotChecked=0, Total=702 [2025-03-16 18:51:10,101 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 21 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:10,101 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 116 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:10,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2025-03-16 18:51:10,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 67. [2025-03-16 18:51:10,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 47 states have (on average 1.0425531914893618) internal successors, (49), 45 states have internal predecessors, (49), 11 states have call successors, (11), 8 states have call predecessors, (11), 8 states have return successors, (30), 13 states have call predecessors, (30), 11 states have call successors, (30) [2025-03-16 18:51:10,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 90 transitions. [2025-03-16 18:51:10,112 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 90 transitions. Word has length 405 [2025-03-16 18:51:10,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:10,113 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 90 transitions. [2025-03-16 18:51:10,113 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.611111111111111) internal successors, (65), 18 states have internal predecessors, (65), 14 states have call successors, (18), 2 states have call predecessors, (18), 8 states have return successors, (23), 7 states have call predecessors, (23), 14 states have call successors, (23) [2025-03-16 18:51:10,113 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 90 transitions. [2025-03-16 18:51:10,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 352 [2025-03-16 18:51:10,116 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:10,116 INFO L218 NwaCegarLoop]: trace histogram [51, 51, 41, 25, 25, 25, 25, 25, 25, 25, 16, 10, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:10,123 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:10,317 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:10,317 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:10,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:10,317 INFO L85 PathProgramCache]: Analyzing trace with hash 1992572321, now seen corresponding path program 6 times [2025-03-16 18:51:10,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:10,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44848064] [2025-03-16 18:51:10,318 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:51:10,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:10,330 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 351 statements into 41 equivalence classes. [2025-03-16 18:51:10,355 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 20 check-sat command(s) and asserted 164 of 351 statements. [2025-03-16 18:51:10,355 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 20 check-sat command(s) [2025-03-16 18:51:10,355 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:10,549 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 365 proven. 1129 refuted. 0 times theorem prover too weak. 5626 trivial. 0 not checked. [2025-03-16 18:51:10,550 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:10,550 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44848064] [2025-03-16 18:51:10,550 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [44848064] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:10,550 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1006579116] [2025-03-16 18:51:10,550 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-16 18:51:10,550 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:10,550 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:10,552 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:51:10,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-16 18:51:10,621 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 351 statements into 41 equivalence classes. [2025-03-16 18:51:10,660 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 20 check-sat command(s) and asserted 164 of 351 statements. [2025-03-16 18:51:10,660 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 20 check-sat command(s) [2025-03-16 18:51:10,660 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:10,662 INFO L256 TraceCheckSpWp]: Trace formula consists of 385 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-16 18:51:10,665 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:10,721 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 356 proven. 1124 refuted. 0 times theorem prover too weak. 5640 trivial. 0 not checked. [2025-03-16 18:51:10,722 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:11,893 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 360 proven. 1160 refuted. 0 times theorem prover too weak. 5600 trivial. 0 not checked. [2025-03-16 18:51:11,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1006579116] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:11,893 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:11,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10, 15] total 19 [2025-03-16 18:51:11,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1944719620] [2025-03-16 18:51:11,893 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:11,894 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-16 18:51:11,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:11,894 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-16 18:51:11,895 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=250, Unknown=0, NotChecked=0, Total=342 [2025-03-16 18:51:11,895 INFO L87 Difference]: Start difference. First operand 67 states and 90 transitions. Second operand has 19 states, 19 states have (on average 3.1578947368421053) internal successors, (60), 19 states have internal predecessors, (60), 13 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) [2025-03-16 18:51:12,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:12,103 INFO L93 Difference]: Finished difference Result 238 states and 367 transitions. [2025-03-16 18:51:12,105 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-03-16 18:51:12,106 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.1578947368421053) internal successors, (60), 19 states have internal predecessors, (60), 13 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) Word has length 351 [2025-03-16 18:51:12,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:12,110 INFO L225 Difference]: With dead ends: 238 [2025-03-16 18:51:12,110 INFO L226 Difference]: Without dead ends: 232 [2025-03-16 18:51:12,110 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 722 GetRequests, 693 SyntacticMatches, 5 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=211, Invalid=439, Unknown=0, NotChecked=0, Total=650 [2025-03-16 18:51:12,111 INFO L435 NwaCegarLoop]: 21 mSDtfsCounter, 88 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 192 mSolverCounterSat, 87 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 87 IncrementalHoareTripleChecker+Valid, 192 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:12,112 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 107 Invalid, 279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [87 Valid, 192 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-16 18:51:12,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 232 states. [2025-03-16 18:51:12,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 232 to 177. [2025-03-16 18:51:12,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 120 states have (on average 1.0333333333333334) internal successors, (124), 116 states have internal predecessors, (124), 36 states have call successors, (36), 19 states have call predecessors, (36), 20 states have return successors, (104), 41 states have call predecessors, (104), 36 states have call successors, (104) [2025-03-16 18:51:12,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 264 transitions. [2025-03-16 18:51:12,145 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 264 transitions. Word has length 351 [2025-03-16 18:51:12,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:12,145 INFO L471 AbstractCegarLoop]: Abstraction has 177 states and 264 transitions. [2025-03-16 18:51:12,145 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.1578947368421053) internal successors, (60), 19 states have internal predecessors, (60), 13 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 11 states have call predecessors, (22), 13 states have call successors, (22) [2025-03-16 18:51:12,146 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 264 transitions. [2025-03-16 18:51:12,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1047 [2025-03-16 18:51:12,152 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:12,153 INFO L218 NwaCegarLoop]: trace histogram [153, 153, 124, 76, 76, 76, 76, 76, 76, 76, 48, 29, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:12,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-16 18:51:12,353 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:12,353 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:12,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:12,354 INFO L85 PathProgramCache]: Analyzing trace with hash 1661394192, now seen corresponding path program 7 times [2025-03-16 18:51:12,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:12,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [614261949] [2025-03-16 18:51:12,354 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:51:12,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:12,371 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1046 statements into 1 equivalence classes. [2025-03-16 18:51:12,481 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1046 of 1046 statements. [2025-03-16 18:51:12,481 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:12,481 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:14,238 INFO L134 CoverageAnalysis]: Checked inductivity of 65538 backedges. 3550 proven. 8135 refuted. 0 times theorem prover too weak. 53853 trivial. 0 not checked. [2025-03-16 18:51:14,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:14,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [614261949] [2025-03-16 18:51:14,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [614261949] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:14,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1592301311] [2025-03-16 18:51:14,239 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-16 18:51:14,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:14,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:14,242 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:51:14,242 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-16 18:51:14,353 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1046 statements into 1 equivalence classes. [2025-03-16 18:51:14,522 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1046 of 1046 statements. [2025-03-16 18:51:14,522 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-16 18:51:14,522 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:14,533 INFO L256 TraceCheckSpWp]: Trace formula consists of 2343 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-03-16 18:51:14,546 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:14,680 INFO L134 CoverageAnalysis]: Checked inductivity of 65538 backedges. 4196 proven. 8973 refuted. 0 times theorem prover too weak. 52369 trivial. 0 not checked. [2025-03-16 18:51:14,681 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-16 18:51:20,026 INFO L134 CoverageAnalysis]: Checked inductivity of 65538 backedges. 4196 proven. 9120 refuted. 0 times theorem prover too weak. 52222 trivial. 0 not checked. [2025-03-16 18:51:20,027 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1592301311] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-16 18:51:20,027 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-16 18:51:20,027 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21, 35] total 40 [2025-03-16 18:51:20,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [977577074] [2025-03-16 18:51:20,027 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-16 18:51:20,029 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 40 states [2025-03-16 18:51:20,029 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-16 18:51:20,030 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2025-03-16 18:51:20,030 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=251, Invalid=1309, Unknown=0, NotChecked=0, Total=1560 [2025-03-16 18:51:20,030 INFO L87 Difference]: Start difference. First operand 177 states and 264 transitions. Second operand has 40 states, 40 states have (on average 3.075) internal successors, (123), 40 states have internal predecessors, (123), 34 states have call successors, (39), 1 states have call predecessors, (39), 18 states have return successors, (53), 20 states have call predecessors, (53), 34 states have call successors, (53) [2025-03-16 18:51:20,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-16 18:51:20,700 INFO L93 Difference]: Finished difference Result 330 states and 632 transitions. [2025-03-16 18:51:20,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2025-03-16 18:51:20,701 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 3.075) internal successors, (123), 40 states have internal predecessors, (123), 34 states have call successors, (39), 1 states have call predecessors, (39), 18 states have return successors, (53), 20 states have call predecessors, (53), 34 states have call successors, (53) Word has length 1046 [2025-03-16 18:51:20,702 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-16 18:51:20,704 INFO L225 Difference]: With dead ends: 330 [2025-03-16 18:51:20,704 INFO L226 Difference]: Without dead ends: 158 [2025-03-16 18:51:20,707 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2159 GetRequests, 2068 SyntacticMatches, 17 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1492 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=1360, Invalid=4340, Unknown=0, NotChecked=0, Total=5700 [2025-03-16 18:51:20,708 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 394 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 529 mSolverCounterSat, 329 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 394 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 858 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 329 IncrementalHoareTripleChecker+Valid, 529 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-03-16 18:51:20,709 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [394 Valid, 252 Invalid, 858 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [329 Valid, 529 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-03-16 18:51:20,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2025-03-16 18:51:20,725 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 126. [2025-03-16 18:51:20,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 90 states have (on average 1.0333333333333334) internal successors, (93), 87 states have internal predecessors, (93), 25 states have call successors, (25), 20 states have call predecessors, (25), 10 states have return successors, (64), 18 states have call predecessors, (64), 25 states have call successors, (64) [2025-03-16 18:51:20,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 182 transitions. [2025-03-16 18:51:20,728 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 182 transitions. Word has length 1046 [2025-03-16 18:51:20,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-16 18:51:20,728 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 182 transitions. [2025-03-16 18:51:20,729 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 40 states, 40 states have (on average 3.075) internal successors, (123), 40 states have internal predecessors, (123), 34 states have call successors, (39), 1 states have call predecessors, (39), 18 states have return successors, (53), 20 states have call predecessors, (53), 34 states have call successors, (53) [2025-03-16 18:51:20,729 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 182 transitions. [2025-03-16 18:51:20,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 747 [2025-03-16 18:51:20,732 INFO L210 NwaCegarLoop]: Found error trace [2025-03-16 18:51:20,732 INFO L218 NwaCegarLoop]: trace histogram [109, 109, 88, 54, 54, 54, 54, 54, 54, 54, 34, 21, 1, 1, 1, 1, 1, 1, 1] [2025-03-16 18:51:20,741 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2025-03-16 18:51:20,933 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2025-03-16 18:51:20,933 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-16 18:51:20,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-16 18:51:20,934 INFO L85 PathProgramCache]: Analyzing trace with hash -1850024956, now seen corresponding path program 8 times [2025-03-16 18:51:20,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-16 18:51:20,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1608132721] [2025-03-16 18:51:20,934 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:20,934 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-16 18:51:20,948 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 746 statements into 2 equivalence classes. [2025-03-16 18:51:21,015 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 746 of 746 statements. [2025-03-16 18:51:21,016 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:21,016 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:30,015 INFO L134 CoverageAnalysis]: Checked inductivity of 33096 backedges. 2756 proven. 10117 refuted. 0 times theorem prover too weak. 20223 trivial. 0 not checked. [2025-03-16 18:51:30,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-16 18:51:30,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1608132721] [2025-03-16 18:51:30,015 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1608132721] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-16 18:51:30,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [35313526] [2025-03-16 18:51:30,015 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-16 18:51:30,015 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-16 18:51:30,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-16 18:51:30,017 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-16 18:51:30,018 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-03-16 18:51:30,152 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 746 statements into 2 equivalence classes. [2025-03-16 18:51:30,270 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 746 of 746 statements. [2025-03-16 18:51:30,270 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-16 18:51:30,270 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-16 18:51:30,276 INFO L256 TraceCheckSpWp]: Trace formula consists of 1677 conjuncts, 220 conjuncts are in the unsatisfiable core [2025-03-16 18:51:30,283 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-16 18:51:30,803 INFO L134 CoverageAnalysis]: Checked inductivity of 33096 backedges. 5957 proven. 4942 refuted. 0 times theorem prover too weak. 22197 trivial. 0 not checked. [2025-03-16 18:51:30,803 INFO L312 TraceCheckSpWp]: Computing backward predicates...