./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive-simple/fibo_20-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 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-simple/fibo_20-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 245fc9fd7d1856b9e3a0ba83da5d44244f493f3972910f1b254ef4afd37f84e2 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 14:33:22,154 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 14:33:22,210 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 14:33:22,216 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 14:33:22,218 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 14:33:22,241 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 14:33:22,242 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 14:33:22,242 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 14:33:22,243 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 14:33:22,243 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 14:33:22,243 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 14:33:22,244 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 14:33:22,244 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 14:33:22,244 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 14:33:22,244 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 14:33:22,244 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 14:33:22,245 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 14:33:22,246 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 14:33:22,246 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:33:22,247 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 14:33:22,247 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 14:33:22,248 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 -> 245fc9fd7d1856b9e3a0ba83da5d44244f493f3972910f1b254ef4afd37f84e2 [2025-03-03 14:33:22,469 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 14:33:22,474 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 14:33:22,477 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 14:33:22,478 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 14:33:22,478 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 14:33:22,479 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_20-2.c [2025-03-03 14:33:23,570 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/acb64a5bd/4f13c0b94e7e4aceb211551f34731d0d/FLAG0db63a638 [2025-03-03 14:33:23,769 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 14:33:23,771 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_20-2.c [2025-03-03 14:33:23,788 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/acb64a5bd/4f13c0b94e7e4aceb211551f34731d0d/FLAG0db63a638 [2025-03-03 14:33:23,808 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/acb64a5bd/4f13c0b94e7e4aceb211551f34731d0d [2025-03-03 14:33:23,824 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 14:33:23,826 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 14:33:23,831 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 14:33:23,831 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 14:33:23,835 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 14:33:23,836 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:23,836 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@96a702a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23, skipping insertion in model container [2025-03-03 14:33:23,836 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:23,845 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 14:33:23,955 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-simple/fibo_20-2.c[745,758] [2025-03-03 14:33:23,957 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:33:23,963 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 14:33:23,973 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-simple/fibo_20-2.c[745,758] [2025-03-03 14:33:23,974 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 14:33:23,985 INFO L204 MainTranslator]: Completed translation [2025-03-03 14:33:23,987 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23 WrapperNode [2025-03-03 14:33:23,988 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 14:33:23,989 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 14:33:23,989 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 14:33:23,989 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 14:33:23,994 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:23,998 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,008 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2025-03-03 14:33:24,008 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 14:33:24,009 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 14:33:24,009 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 14:33:24,009 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 14:33:24,013 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,013 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,014 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,020 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-03 14:33:24,020 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,020 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,021 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,022 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,022 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,023 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,023 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 14:33:24,024 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 14:33:24,024 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 14:33:24,024 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 14:33:24,024 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (1/1) ... [2025-03-03 14:33:24,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 14:33:24,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:24,047 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-03 14:33:24,049 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-03 14:33:24,064 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 14:33:24,065 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 14:33:24,065 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 14:33:24,065 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 14:33:24,065 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2025-03-03 14:33:24,065 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2025-03-03 14:33:24,103 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 14:33:24,105 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 14:33:24,165 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2025-03-03 14:33:24,170 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2025-03-03 14:33:24,170 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 14:33:24,176 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 14:33:24,177 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 14:33:24,177 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:33:24 BoogieIcfgContainer [2025-03-03 14:33:24,178 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 14:33:24,179 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 14:33:24,179 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 14:33:24,182 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 14:33:24,182 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 02:33:23" (1/3) ... [2025-03-03 14:33:24,183 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63e4dc97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:33:24, skipping insertion in model container [2025-03-03 14:33:24,183 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 02:33:23" (2/3) ... [2025-03-03 14:33:24,183 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63e4dc97 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 02:33:24, skipping insertion in model container [2025-03-03 14:33:24,183 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 02:33:24" (3/3) ... [2025-03-03 14:33:24,184 INFO L128 eAbstractionObserver]: Analyzing ICFG fibo_20-2.c [2025-03-03 14:33:24,193 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 14:33:24,194 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG fibo_20-2.c that has 2 procedures, 20 locations, 1 initial locations, 0 loop locations, and 1 error locations. [2025-03-03 14:33:24,224 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 14:33:24,233 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;@69b2b943, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 14:33:24,235 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-03-03 14:33:24,238 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 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-03 14:33:24,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 14:33:24,241 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:24,242 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:24,242 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:24,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:24,247 INFO L85 PathProgramCache]: Analyzing trace with hash 402921910, now seen corresponding path program 1 times [2025-03-03 14:33:24,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:24,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [808014865] [2025-03-03 14:33:24,254 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:24,254 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:24,301 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 14:33:24,318 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 14:33:24,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:24,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:24,419 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-03 14:33:24,420 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:24,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [808014865] [2025-03-03 14:33:24,422 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [808014865] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:33:24,422 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:33:24,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:33:24,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1527113326] [2025-03-03 14:33:24,424 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:33:24,426 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:33:24,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:24,440 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:33:24,441 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:33:24,442 INFO L87 Difference]: Start difference. First operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 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, 4 states have (on average 2.0) 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-03 14:33:24,511 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:24,512 INFO L93 Difference]: Finished difference Result 32 states and 40 transitions. [2025-03-03 14:33:24,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:33:24,514 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) 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-03 14:33:24,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:24,518 INFO L225 Difference]: With dead ends: 32 [2025-03-03 14:33:24,519 INFO L226 Difference]: Without dead ends: 20 [2025-03-03 14:33:24,521 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-03 14:33:24,524 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 10 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:24,525 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 51 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:24,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-03 14:33:24,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 18. [2025-03-03 14:33:24,545 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-03 14:33:24,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2025-03-03 14:33:24,548 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 10 [2025-03-03 14:33:24,549 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:24,549 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2025-03-03 14:33:24,549 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) 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-03 14:33:24,550 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2025-03-03 14:33:24,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-03-03 14:33:24,550 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:24,550 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:24,551 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 14:33:24,551 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:24,551 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:24,551 INFO L85 PathProgramCache]: Analyzing trace with hash -2143228819, now seen corresponding path program 1 times [2025-03-03 14:33:24,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:24,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1990302832] [2025-03-03 14:33:24,552 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:24,552 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:24,556 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-03-03 14:33:24,563 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-03-03 14:33:24,564 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:24,564 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:24,610 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-03 14:33:24,610 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:24,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1990302832] [2025-03-03 14:33:24,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1990302832] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 14:33:24,610 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 14:33:24,611 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 14:33:24,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1335374359] [2025-03-03 14:33:24,611 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 14:33:24,612 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-03-03 14:33:24,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:24,612 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-03-03 14:33:24,612 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-03-03 14:33:24,612 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 5 states, 4 states have (on average 2.25) 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-03 14:33:24,643 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:24,643 INFO L93 Difference]: Finished difference Result 24 states and 29 transitions. [2025-03-03 14:33:24,643 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-03-03 14:33:24,643 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.25) 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-03 14:33:24,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:24,644 INFO L225 Difference]: With dead ends: 24 [2025-03-03 14:33:24,644 INFO L226 Difference]: Without dead ends: 20 [2025-03-03 14:33:24,644 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-03 14:33:24,645 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 7 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:24,645 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 34 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:33:24,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-03 14:33:24,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 18. [2025-03-03 14:33:24,648 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-03 14:33:24,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2025-03-03 14:33:24,648 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 11 [2025-03-03 14:33:24,648 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:24,648 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2025-03-03 14:33:24,648 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.25) 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-03 14:33:24,648 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2025-03-03 14:33:24,649 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2025-03-03 14:33:24,649 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:24,649 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-03 14:33:24,649 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 14:33:24,649 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:24,649 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:24,649 INFO L85 PathProgramCache]: Analyzing trace with hash -1857137997, now seen corresponding path program 1 times [2025-03-03 14:33:24,650 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:24,650 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [334502312] [2025-03-03 14:33:24,650 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:24,650 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:24,656 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:33:24,664 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:33:24,667 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:24,668 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:24,764 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-03 14:33:24,764 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:24,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [334502312] [2025-03-03 14:33:24,764 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [334502312] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:24,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [325408563] [2025-03-03 14:33:24,765 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:24,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:24,765 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:24,767 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-03 14:33:24,768 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-03 14:33:24,797 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 23 statements into 1 equivalence classes. [2025-03-03 14:33:24,812 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 23 of 23 statements. [2025-03-03 14:33:24,813 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:24,813 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:24,814 INFO L256 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 14:33:24,817 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:24,897 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-03 14:33:24,898 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:25,115 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-03 14:33:25,116 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [325408563] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:25,116 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:25,116 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 11 [2025-03-03 14:33:25,116 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [918708854] [2025-03-03 14:33:25,116 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:25,116 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 14:33:25,116 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:25,117 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 14:33:25,117 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:33:25,117 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 11 states, 8 states have (on average 3.5) internal successors, (28), 11 states have internal predecessors, (28), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 14:33:25,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:25,193 INFO L93 Difference]: Finished difference Result 35 states and 46 transitions. [2025-03-03 14:33:25,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-03-03 14:33:25,193 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 8 states have (on average 3.5) internal successors, (28), 11 states have internal predecessors, (28), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 23 [2025-03-03 14:33:25,193 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:25,193 INFO L225 Difference]: With dead ends: 35 [2025-03-03 14:33:25,194 INFO L226 Difference]: Without dead ends: 20 [2025-03-03 14:33:25,194 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=112, Unknown=0, NotChecked=0, Total=156 [2025-03-03 14:33:25,194 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 9 mSDsluCounter, 47 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 60 SdHoareTripleChecker+Invalid, 75 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:25,194 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 60 Invalid, 75 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:25,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-03-03 14:33:25,199 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-03-03 14:33:25,199 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 15 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2025-03-03 14:33:25,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 24 transitions. [2025-03-03 14:33:25,200 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 24 transitions. Word has length 23 [2025-03-03 14:33:25,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:25,200 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 24 transitions. [2025-03-03 14:33:25,200 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 8 states have (on average 3.5) internal successors, (28), 11 states have internal predecessors, (28), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 14:33:25,201 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 24 transitions. [2025-03-03 14:33:25,201 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-03-03 14:33:25,201 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:25,201 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:25,207 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 14:33:25,405 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-03 14:33:25,405 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:25,406 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:25,406 INFO L85 PathProgramCache]: Analyzing trace with hash -318077138, now seen corresponding path program 1 times [2025-03-03 14:33:25,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:25,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [927152739] [2025-03-03 14:33:25,406 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:25,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:25,414 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-03 14:33:25,419 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-03 14:33:25,419 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:25,419 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:25,500 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-03 14:33:25,500 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:25,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [927152739] [2025-03-03 14:33:25,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [927152739] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:25,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [44845685] [2025-03-03 14:33:25,501 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 14:33:25,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:25,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:25,504 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-03 14:33:25,504 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-03 14:33:25,525 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 24 statements into 1 equivalence classes. [2025-03-03 14:33:25,534 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 24 of 24 statements. [2025-03-03 14:33:25,534 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:25,534 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:25,535 INFO L256 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 14:33:25,535 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:25,564 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-03-03 14:33:25,564 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:25,709 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 8 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-03 14:33:25,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [44845685] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:25,709 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:25,710 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 9 [2025-03-03 14:33:25,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1349754646] [2025-03-03 14:33:25,710 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:25,710 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-03-03 14:33:25,710 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:25,710 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-03 14:33:25,711 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2025-03-03 14:33:25,711 INFO L87 Difference]: Start difference. First operand 20 states and 24 transitions. Second operand has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:33:25,765 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:25,765 INFO L93 Difference]: Finished difference Result 29 states and 38 transitions. [2025-03-03 14:33:25,765 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 14:33:25,765 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) Word has length 24 [2025-03-03 14:33:25,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:25,766 INFO L225 Difference]: With dead ends: 29 [2025-03-03 14:33:25,767 INFO L226 Difference]: Without dead ends: 25 [2025-03-03 14:33:25,767 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 45 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2025-03-03 14:33:25,768 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 21 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:25,768 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 37 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:33:25,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2025-03-03 14:33:25,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2025-03-03 14:33:25,771 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-03 14:33:25,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 34 transitions. [2025-03-03 14:33:25,772 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 34 transitions. Word has length 24 [2025-03-03 14:33:25,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:25,772 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 34 transitions. [2025-03-03 14:33:25,772 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 9 states have internal predecessors, (23), 5 states have call successors, (5), 1 states have call predecessors, (5), 3 states have return successors, (5), 2 states have call predecessors, (5), 5 states have call successors, (5) [2025-03-03 14:33:25,773 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 34 transitions. [2025-03-03 14:33:25,773 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-03-03 14:33:25,773 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:25,773 INFO L218 NwaCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:25,779 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 14:33:25,974 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-03 14:33:25,974 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:25,974 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:25,975 INFO L85 PathProgramCache]: Analyzing trace with hash -896080901, now seen corresponding path program 2 times [2025-03-03 14:33:25,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:25,975 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1317919305] [2025-03-03 14:33:25,975 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:33:25,975 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:25,979 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 37 statements into 2 equivalence classes. [2025-03-03 14:33:25,984 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:33:25,984 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:33:25,984 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:26,112 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 24 proven. 7 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2025-03-03 14:33:26,113 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:26,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1317919305] [2025-03-03 14:33:26,113 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1317919305] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:26,113 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [488569898] [2025-03-03 14:33:26,113 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:33:26,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:26,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:26,116 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-03 14:33:26,117 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-03 14:33:26,138 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 37 statements into 2 equivalence classes. [2025-03-03 14:33:26,149 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 37 of 37 statements. [2025-03-03 14:33:26,149 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:33:26,149 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:26,150 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 14:33:26,152 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:26,226 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 6 proven. 21 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2025-03-03 14:33:26,226 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:26,506 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 6 proven. 28 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2025-03-03 14:33:26,507 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [488569898] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:26,507 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:26,507 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 9] total 18 [2025-03-03 14:33:26,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003861561] [2025-03-03 14:33:26,507 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:26,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2025-03-03 14:33:26,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:26,508 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2025-03-03 14:33:26,508 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2025-03-03 14:33:26,508 INFO L87 Difference]: Start difference. First operand 25 states and 34 transitions. Second operand has 18 states, 16 states have (on average 2.8125) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) [2025-03-03 14:33:26,698 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:26,699 INFO L93 Difference]: Finished difference Result 60 states and 93 transitions. [2025-03-03 14:33:26,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-03 14:33:26,700 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 2.8125) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) Word has length 37 [2025-03-03 14:33:26,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:26,701 INFO L225 Difference]: With dead ends: 60 [2025-03-03 14:33:26,701 INFO L226 Difference]: Without dead ends: 38 [2025-03-03 14:33:26,701 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 65 SyntacticMatches, 3 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 112 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=168, Invalid=482, Unknown=0, NotChecked=0, Total=650 [2025-03-03 14:33:26,702 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 52 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:26,702 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 95 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:26,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2025-03-03 14:33:26,710 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2025-03-03 14:33:26,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 27 states have (on average 1.1111111111111112) internal successors, (30), 26 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 5 states have return successors, (11), 7 states have call predecessors, (11), 5 states have call successors, (11) [2025-03-03 14:33:26,711 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2025-03-03 14:33:26,711 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 37 [2025-03-03 14:33:26,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:26,711 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2025-03-03 14:33:26,712 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 2.8125) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) [2025-03-03 14:33:26,712 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2025-03-03 14:33:26,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2025-03-03 14:33:26,714 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:26,714 INFO L218 NwaCegarLoop]: trace histogram [13, 13, 11, 6, 6, 6, 6, 6, 6, 6, 5, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:26,721 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-03 14:33:26,914 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-03 14:33:26,915 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:26,915 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:26,915 INFO L85 PathProgramCache]: Analyzing trace with hash 1467785241, now seen corresponding path program 3 times [2025-03-03 14:33:26,915 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:26,915 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1205598134] [2025-03-03 14:33:26,915 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:33:26,915 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:26,921 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 93 statements into 12 equivalence classes. [2025-03-03 14:33:26,935 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 59 of 93 statements. [2025-03-03 14:33:26,936 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-03 14:33:26,936 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:27,032 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 174 proven. 17 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2025-03-03 14:33:27,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:27,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1205598134] [2025-03-03 14:33:27,033 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1205598134] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:27,033 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627676967] [2025-03-03 14:33:27,033 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:33:27,033 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:27,033 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:27,035 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-03 14:33:27,036 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-03 14:33:27,062 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 93 statements into 12 equivalence classes. [2025-03-03 14:33:27,093 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) and asserted 59 of 93 statements. [2025-03-03 14:33:27,093 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2025-03-03 14:33:27,093 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:27,094 INFO L256 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-03 14:33:27,096 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:27,122 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 174 proven. 17 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2025-03-03 14:33:27,123 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:27,436 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 174 proven. 18 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2025-03-03 14:33:27,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627676967] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:27,436 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:27,437 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 11 [2025-03-03 14:33:27,437 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [64634628] [2025-03-03 14:33:27,437 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:27,437 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-03-03 14:33:27,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:27,437 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-03-03 14:33:27,437 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2025-03-03 14:33:27,438 INFO L87 Difference]: Start difference. First operand 38 states and 46 transitions. Second operand has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (10), 6 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-03 14:33:27,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:27,516 INFO L93 Difference]: Finished difference Result 72 states and 93 transitions. [2025-03-03 14:33:27,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-03-03 14:33:27,517 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (10), 6 states have call predecessors, (10), 4 states have call successors, (10) Word has length 93 [2025-03-03 14:33:27,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:27,518 INFO L225 Difference]: With dead ends: 72 [2025-03-03 14:33:27,518 INFO L226 Difference]: Without dead ends: 40 [2025-03-03 14:33:27,518 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 180 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2025-03-03 14:33:27,518 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 17 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:27,519 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 84 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:33:27,519 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-03-03 14:33:27,522 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2025-03-03 14:33:27,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 29 states have (on average 1.103448275862069) internal successors, (32), 27 states have internal predecessors, (32), 5 states have call successors, (5), 5 states have call predecessors, (5), 5 states have return successors, (10), 7 states have call predecessors, (10), 5 states have call successors, (10) [2025-03-03 14:33:27,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 47 transitions. [2025-03-03 14:33:27,524 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 47 transitions. Word has length 93 [2025-03-03 14:33:27,525 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:27,525 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 47 transitions. [2025-03-03 14:33:27,525 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.4545454545454546) internal successors, (38), 11 states have internal predecessors, (38), 4 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (10), 6 states have call predecessors, (10), 4 states have call successors, (10) [2025-03-03 14:33:27,525 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 47 transitions. [2025-03-03 14:33:27,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-03-03 14:33:27,525 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:27,527 INFO L218 NwaCegarLoop]: trace histogram [9, 9, 7, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:27,533 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-03-03 14:33:27,732 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-03 14:33:27,733 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:27,733 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:27,733 INFO L85 PathProgramCache]: Analyzing trace with hash 152396661, now seen corresponding path program 4 times [2025-03-03 14:33:27,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:27,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1471380064] [2025-03-03 14:33:27,733 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:33:27,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:27,737 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 65 statements into 2 equivalence classes. [2025-03-03 14:33:27,743 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 65 of 65 statements. [2025-03-03 14:33:27,743 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-03 14:33:27,743 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:27,864 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 96 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2025-03-03 14:33:27,864 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:27,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1471380064] [2025-03-03 14:33:27,864 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1471380064] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:27,864 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1474181494] [2025-03-03 14:33:27,864 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:33:27,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:27,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:27,866 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-03 14:33:27,868 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-03 14:33:27,896 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 65 statements into 2 equivalence classes. [2025-03-03 14:33:27,914 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 65 of 65 statements. [2025-03-03 14:33:27,915 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-03-03 14:33:27,915 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:27,916 INFO L256 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-03 14:33:27,917 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:27,968 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 88 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-03-03 14:33:27,969 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:28,355 INFO L134 CoverageAnalysis]: Checked inductivity of 189 backedges. 17 proven. 103 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2025-03-03 14:33:28,356 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1474181494] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:28,356 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:28,356 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8, 11] total 17 [2025-03-03 14:33:28,356 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228403105] [2025-03-03 14:33:28,356 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:28,356 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:33:28,356 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:28,357 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:33:28,357 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=203, Unknown=0, NotChecked=0, Total=272 [2025-03-03 14:33:28,357 INFO L87 Difference]: Start difference. First operand 40 states and 47 transitions. Second operand has 17 states, 14 states have (on average 3.357142857142857) internal successors, (47), 17 states have internal predecessors, (47), 13 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-03-03 14:33:28,521 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:28,521 INFO L93 Difference]: Finished difference Result 89 states and 122 transitions. [2025-03-03 14:33:28,521 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-03 14:33:28,521 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 3.357142857142857) internal successors, (47), 17 states have internal predecessors, (47), 13 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) Word has length 65 [2025-03-03 14:33:28,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:28,524 INFO L225 Difference]: With dead ends: 89 [2025-03-03 14:33:28,524 INFO L226 Difference]: Without dead ends: 85 [2025-03-03 14:33:28,524 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 121 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=138, Invalid=324, Unknown=0, NotChecked=0, Total=462 [2025-03-03 14:33:28,525 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 47 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 218 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:28,525 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 97 Invalid, 218 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:28,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2025-03-03 14:33:28,534 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 79. [2025-03-03 14:33:28,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 54 states have (on average 1.1111111111111112) internal successors, (60), 51 states have internal predecessors, (60), 14 states have call successors, (14), 8 states have call predecessors, (14), 10 states have return successors, (34), 19 states have call predecessors, (34), 14 states have call successors, (34) [2025-03-03 14:33:28,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 108 transitions. [2025-03-03 14:33:28,537 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 108 transitions. Word has length 65 [2025-03-03 14:33:28,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:28,537 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 108 transitions. [2025-03-03 14:33:28,537 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 3.357142857142857) internal successors, (47), 17 states have internal predecessors, (47), 13 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 7 states have call predecessors, (16), 13 states have call successors, (16) [2025-03-03 14:33:28,538 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 108 transitions. [2025-03-03 14:33:28,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 270 [2025-03-03 14:33:28,540 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:28,540 INFO L218 NwaCegarLoop]: trace histogram [39, 39, 31, 19, 19, 19, 19, 19, 19, 19, 12, 8, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:28,547 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-03 14:33:28,746 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-03 14:33:28,746 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:28,746 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:28,746 INFO L85 PathProgramCache]: Analyzing trace with hash -1241057303, now seen corresponding path program 5 times [2025-03-03 14:33:28,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:28,746 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218375425] [2025-03-03 14:33:28,746 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-03 14:33:28,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:28,755 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 269 statements into 30 equivalence classes. [2025-03-03 14:33:28,782 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) and asserted 190 of 269 statements. [2025-03-03 14:33:28,783 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) [2025-03-03 14:33:28,783 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:29,127 INFO L134 CoverageAnalysis]: Checked inductivity of 4113 backedges. 409 proven. 906 refuted. 0 times theorem prover too weak. 2798 trivial. 0 not checked. [2025-03-03 14:33:29,127 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:29,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218375425] [2025-03-03 14:33:29,127 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1218375425] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:29,127 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [942190079] [2025-03-03 14:33:29,127 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-03 14:33:29,127 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:29,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:29,129 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-03 14:33:29,130 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-03 14:33:29,169 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 269 statements into 30 equivalence classes. [2025-03-03 14:33:29,211 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) and asserted 190 of 269 statements. [2025-03-03 14:33:29,211 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 22 check-sat command(s) [2025-03-03 14:33:29,211 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:29,213 INFO L256 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-03 14:33:29,224 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:29,296 INFO L134 CoverageAnalysis]: Checked inductivity of 4113 backedges. 2372 proven. 241 refuted. 0 times theorem prover too weak. 1500 trivial. 0 not checked. [2025-03-03 14:33:29,296 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:30,564 INFO L134 CoverageAnalysis]: Checked inductivity of 4113 backedges. 413 proven. 1025 refuted. 0 times theorem prover too weak. 2675 trivial. 0 not checked. [2025-03-03 14:33:30,565 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [942190079] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:30,565 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:30,565 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12, 17] total 24 [2025-03-03 14:33:30,565 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2034053718] [2025-03-03 14:33:30,565 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:30,566 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-03-03 14:33:30,566 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:30,566 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-03-03 14:33:30,566 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=413, Unknown=0, NotChecked=0, Total=552 [2025-03-03 14:33:30,567 INFO L87 Difference]: Start difference. First operand 79 states and 108 transitions. Second operand has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 24 states have internal predecessors, (77), 18 states have call successors, (25), 2 states have call predecessors, (25), 9 states have return successors, (31), 13 states have call predecessors, (31), 18 states have call successors, (31) [2025-03-03 14:33:30,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:30,794 INFO L93 Difference]: Finished difference Result 185 states and 289 transitions. [2025-03-03 14:33:30,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-03 14:33:30,794 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 24 states have internal predecessors, (77), 18 states have call successors, (25), 2 states have call predecessors, (25), 9 states have return successors, (31), 13 states have call predecessors, (31), 18 states have call successors, (31) Word has length 269 [2025-03-03 14:33:30,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:30,796 INFO L225 Difference]: With dead ends: 185 [2025-03-03 14:33:30,796 INFO L226 Difference]: Without dead ends: 84 [2025-03-03 14:33:30,798 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 569 GetRequests, 525 SyntacticMatches, 8 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 428 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=386, Invalid=1020, Unknown=0, NotChecked=0, Total=1406 [2025-03-03 14:33:30,799 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 72 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 248 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 119 SdHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 248 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:30,800 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 119 Invalid, 323 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 248 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:30,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2025-03-03 14:33:30,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 78. [2025-03-03 14:33:30,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 54 states have (on average 1.0555555555555556) internal successors, (57), 52 states have internal predecessors, (57), 13 states have call successors, (13), 8 states have call predecessors, (13), 10 states have return successors, (33), 17 states have call predecessors, (33), 13 states have call successors, (33) [2025-03-03 14:33:30,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 103 transitions. [2025-03-03 14:33:30,813 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 103 transitions. Word has length 269 [2025-03-03 14:33:30,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:30,813 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 103 transitions. [2025-03-03 14:33:30,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 3.2083333333333335) internal successors, (77), 24 states have internal predecessors, (77), 18 states have call successors, (25), 2 states have call predecessors, (25), 9 states have return successors, (31), 13 states have call predecessors, (31), 18 states have call successors, (31) [2025-03-03 14:33:30,814 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 103 transitions. [2025-03-03 14:33:30,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 216 [2025-03-03 14:33:30,819 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:30,819 INFO L218 NwaCegarLoop]: trace histogram [31, 31, 25, 15, 15, 15, 15, 15, 15, 15, 10, 6, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:30,825 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-03-03 14:33:31,019 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-03 14:33:31,019 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:31,020 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:31,020 INFO L85 PathProgramCache]: Analyzing trace with hash -555793953, now seen corresponding path program 6 times [2025-03-03 14:33:31,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:31,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1015456924] [2025-03-03 14:33:31,020 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-03 14:33:31,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:31,026 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 215 statements into 28 equivalence classes. [2025-03-03 14:33:31,039 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 16 check-sat command(s) and asserted 125 of 215 statements. [2025-03-03 14:33:31,039 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 16 check-sat command(s) [2025-03-03 14:33:31,040 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:31,163 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 241 proven. 445 refuted. 0 times theorem prover too weak. 1894 trivial. 0 not checked. [2025-03-03 14:33:31,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:31,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1015456924] [2025-03-03 14:33:31,164 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1015456924] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:31,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1751144354] [2025-03-03 14:33:31,165 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-03 14:33:31,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:31,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:31,167 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-03 14:33:31,168 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-03 14:33:31,213 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 215 statements into 28 equivalence classes. [2025-03-03 14:33:31,240 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 16 check-sat command(s) and asserted 125 of 215 statements. [2025-03-03 14:33:31,240 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 16 check-sat command(s) [2025-03-03 14:33:31,240 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:31,241 INFO L256 TraceCheckSpWp]: Trace formula consists of 298 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-03 14:33:31,245 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:31,290 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 241 proven. 445 refuted. 0 times theorem prover too weak. 1894 trivial. 0 not checked. [2025-03-03 14:33:31,290 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:32,016 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 243 proven. 467 refuted. 0 times theorem prover too weak. 1870 trivial. 0 not checked. [2025-03-03 14:33:32,017 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1751144354] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:32,018 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:32,018 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 13] total 15 [2025-03-03 14:33:32,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1924450854] [2025-03-03 14:33:32,018 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:32,018 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2025-03-03 14:33:32,018 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:32,019 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-03 14:33:32,019 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=152, Unknown=0, NotChecked=0, Total=210 [2025-03-03 14:33:32,019 INFO L87 Difference]: Start difference. First operand 78 states and 103 transitions. Second operand has 15 states, 13 states have (on average 3.5384615384615383) internal successors, (46), 15 states have internal predecessors, (46), 10 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2025-03-03 14:33:32,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:32,089 INFO L93 Difference]: Finished difference Result 93 states and 133 transitions. [2025-03-03 14:33:32,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 14:33:32,090 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 3.5384615384615383) internal successors, (46), 15 states have internal predecessors, (46), 10 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) Word has length 215 [2025-03-03 14:33:32,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:32,091 INFO L225 Difference]: With dead ends: 93 [2025-03-03 14:33:32,091 INFO L226 Difference]: Without dead ends: 89 [2025-03-03 14:33:32,091 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 445 GetRequests, 423 SyntacticMatches, 5 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2025-03-03 14:33:32,092 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 17 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:32,092 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 86 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 14:33:32,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2025-03-03 14:33:32,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 81. [2025-03-03 14:33:32,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 56 states have (on average 1.0535714285714286) internal successors, (59), 54 states have internal predecessors, (59), 13 states have call successors, (13), 8 states have call predecessors, (13), 11 states have return successors, (36), 18 states have call predecessors, (36), 13 states have call successors, (36) [2025-03-03 14:33:32,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 108 transitions. [2025-03-03 14:33:32,100 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 108 transitions. Word has length 215 [2025-03-03 14:33:32,100 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:32,100 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 108 transitions. [2025-03-03 14:33:32,100 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 3.5384615384615383) internal successors, (46), 15 states have internal predecessors, (46), 10 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2025-03-03 14:33:32,100 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 108 transitions. [2025-03-03 14:33:32,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 285 [2025-03-03 14:33:32,102 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:32,103 INFO L218 NwaCegarLoop]: trace histogram [41, 41, 34, 20, 20, 20, 20, 20, 20, 20, 14, 7, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:32,108 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-03-03 14:33:32,303 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-03 14:33:32,303 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:32,303 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:32,304 INFO L85 PathProgramCache]: Analyzing trace with hash -2062059334, now seen corresponding path program 7 times [2025-03-03 14:33:32,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:32,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [625148552] [2025-03-03 14:33:32,304 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-03 14:33:32,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:32,310 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 284 statements into 1 equivalence classes. [2025-03-03 14:33:32,324 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 284 of 284 statements. [2025-03-03 14:33:32,325 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:32,325 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:32,548 INFO L134 CoverageAnalysis]: Checked inductivity of 4601 backedges. 168 proven. 990 refuted. 0 times theorem prover too weak. 3443 trivial. 0 not checked. [2025-03-03 14:33:32,548 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:32,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [625148552] [2025-03-03 14:33:32,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [625148552] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:32,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1095057676] [2025-03-03 14:33:32,548 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-03 14:33:32,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:32,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:32,550 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-03 14:33:32,552 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-03 14:33:32,602 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 284 statements into 1 equivalence classes. [2025-03-03 14:33:32,646 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 284 of 284 statements. [2025-03-03 14:33:32,647 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:32,647 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:32,651 INFO L256 TraceCheckSpWp]: Trace formula consists of 649 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-03 14:33:32,654 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:32,701 INFO L134 CoverageAnalysis]: Checked inductivity of 4601 backedges. 168 proven. 990 refuted. 0 times theorem prover too weak. 3443 trivial. 0 not checked. [2025-03-03 14:33:32,701 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:33,726 INFO L134 CoverageAnalysis]: Checked inductivity of 4601 backedges. 168 proven. 1030 refuted. 0 times theorem prover too weak. 3403 trivial. 0 not checked. [2025-03-03 14:33:33,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1095057676] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:33,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:33,727 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10, 15] total 17 [2025-03-03 14:33:33,727 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [270560066] [2025-03-03 14:33:33,727 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:33,727 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-03-03 14:33:33,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:33,728 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-03-03 14:33:33,728 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=198, Unknown=0, NotChecked=0, Total=272 [2025-03-03 14:33:33,729 INFO L87 Difference]: Start difference. First operand 81 states and 108 transitions. Second operand has 17 states, 15 states have (on average 3.466666666666667) internal successors, (52), 17 states have internal predecessors, (52), 14 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (19), 7 states have call predecessors, (19), 14 states have call successors, (19) [2025-03-03 14:33:33,820 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:33,820 INFO L93 Difference]: Finished difference Result 95 states and 144 transitions. [2025-03-03 14:33:33,821 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-03-03 14:33:33,821 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 3.466666666666667) internal successors, (52), 17 states have internal predecessors, (52), 14 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (19), 7 states have call predecessors, (19), 14 states have call successors, (19) Word has length 284 [2025-03-03 14:33:33,821 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:33,822 INFO L225 Difference]: With dead ends: 95 [2025-03-03 14:33:33,822 INFO L226 Difference]: Without dead ends: 91 [2025-03-03 14:33:33,822 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 586 GetRequests, 560 SyntacticMatches, 6 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=144, Invalid=318, Unknown=0, NotChecked=0, Total=462 [2025-03-03 14:33:33,823 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 30 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:33,823 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 76 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:33,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2025-03-03 14:33:33,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 83. [2025-03-03 14:33:33,830 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 57 states have (on average 1.0526315789473684) internal successors, (60), 55 states have internal predecessors, (60), 14 states have call successors, (14), 8 states have call predecessors, (14), 11 states have return successors, (43), 19 states have call predecessors, (43), 14 states have call successors, (43) [2025-03-03 14:33:33,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 117 transitions. [2025-03-03 14:33:33,831 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 117 transitions. Word has length 284 [2025-03-03 14:33:33,831 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:33,831 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 117 transitions. [2025-03-03 14:33:33,831 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 3.466666666666667) internal successors, (52), 17 states have internal predecessors, (52), 14 states have call successors, (15), 1 states have call predecessors, (15), 7 states have return successors, (19), 7 states have call predecessors, (19), 14 states have call successors, (19) [2025-03-03 14:33:33,831 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 117 transitions. [2025-03-03 14:33:33,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 311 [2025-03-03 14:33:33,833 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:33,833 INFO L218 NwaCegarLoop]: trace histogram [45, 45, 36, 22, 22, 22, 22, 22, 22, 22, 14, 9, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:33,839 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-03-03 14:33:34,034 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-03 14:33:34,034 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:34,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:34,035 INFO L85 PathProgramCache]: Analyzing trace with hash -1474401376, now seen corresponding path program 8 times [2025-03-03 14:33:34,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:34,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340848535] [2025-03-03 14:33:34,035 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:33:34,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:34,043 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 310 statements into 2 equivalence classes. [2025-03-03 14:33:34,064 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 310 of 310 statements. [2025-03-03 14:33:34,064 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:33:34,064 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:34,338 INFO L134 CoverageAnalysis]: Checked inductivity of 5514 backedges. 213 proven. 1259 refuted. 0 times theorem prover too weak. 4042 trivial. 0 not checked. [2025-03-03 14:33:34,339 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:34,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [340848535] [2025-03-03 14:33:34,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [340848535] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:34,339 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [534609508] [2025-03-03 14:33:34,339 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:33:34,339 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:34,339 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:34,341 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-03 14:33:34,342 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-03 14:33:34,401 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 310 statements into 2 equivalence classes. [2025-03-03 14:33:34,451 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 310 of 310 statements. [2025-03-03 14:33:34,451 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:33:34,451 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:34,453 INFO L256 TraceCheckSpWp]: Trace formula consists of 707 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-03 14:33:34,456 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:34,509 INFO L134 CoverageAnalysis]: Checked inductivity of 5514 backedges. 213 proven. 1259 refuted. 0 times theorem prover too weak. 4042 trivial. 0 not checked. [2025-03-03 14:33:34,509 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:35,893 INFO L134 CoverageAnalysis]: Checked inductivity of 5514 backedges. 213 proven. 1316 refuted. 0 times theorem prover too weak. 3985 trivial. 0 not checked. [2025-03-03 14:33:35,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [534609508] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:35,893 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:35,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 17] total 19 [2025-03-03 14:33:35,893 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1260080087] [2025-03-03 14:33:35,893 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:35,894 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2025-03-03 14:33:35,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:35,894 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2025-03-03 14:33:35,895 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=250, Unknown=0, NotChecked=0, Total=342 [2025-03-03 14:33:35,895 INFO L87 Difference]: Start difference. First operand 83 states and 117 transitions. Second operand has 19 states, 17 states have (on average 3.411764705882353) internal successors, (58), 19 states have internal predecessors, (58), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) [2025-03-03 14:33:36,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:36,010 INFO L93 Difference]: Finished difference Result 92 states and 137 transitions. [2025-03-03 14:33:36,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-03 14:33:36,011 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 3.411764705882353) internal successors, (58), 19 states have internal predecessors, (58), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) Word has length 310 [2025-03-03 14:33:36,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:36,012 INFO L225 Difference]: With dead ends: 92 [2025-03-03 14:33:36,012 INFO L226 Difference]: Without dead ends: 88 [2025-03-03 14:33:36,013 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 641 GetRequests, 611 SyntacticMatches, 7 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=188, Invalid=412, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:33:36,013 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 36 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:36,013 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 89 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:36,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2025-03-03 14:33:36,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2025-03-03 14:33:36,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 60 states have (on average 1.05) internal successors, (63), 58 states have internal predecessors, (63), 15 states have call successors, (15), 8 states have call predecessors, (15), 12 states have return successors, (55), 21 states have call predecessors, (55), 15 states have call successors, (55) [2025-03-03 14:33:36,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 133 transitions. [2025-03-03 14:33:36,021 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 133 transitions. Word has length 310 [2025-03-03 14:33:36,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:36,022 INFO L471 AbstractCegarLoop]: Abstraction has 88 states and 133 transitions. [2025-03-03 14:33:36,022 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 3.411764705882353) internal successors, (58), 19 states have internal predecessors, (58), 16 states have call successors, (17), 1 states have call predecessors, (17), 8 states have return successors, (22), 8 states have call predecessors, (22), 16 states have call successors, (22) [2025-03-03 14:33:36,022 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 133 transitions. [2025-03-03 14:33:36,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 584 [2025-03-03 14:33:36,044 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:36,044 INFO L218 NwaCegarLoop]: trace histogram [85, 85, 69, 42, 42, 42, 42, 42, 42, 42, 27, 16, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:36,050 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-03-03 14:33:36,248 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:36,248 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:36,248 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:36,249 INFO L85 PathProgramCache]: Analyzing trace with hash -60838961, now seen corresponding path program 9 times [2025-03-03 14:33:36,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:36,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [515414845] [2025-03-03 14:33:36,249 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:33:36,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:36,260 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 583 statements into 78 equivalence classes. [2025-03-03 14:33:36,293 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 32 check-sat command(s) and asserted 245 of 583 statements. [2025-03-03 14:33:36,293 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 32 check-sat command(s) [2025-03-03 14:33:36,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:36,510 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 469 proven. 2966 refuted. 0 times theorem prover too weak. 16635 trivial. 0 not checked. [2025-03-03 14:33:36,511 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:36,511 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [515414845] [2025-03-03 14:33:36,511 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [515414845] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:36,513 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1202581463] [2025-03-03 14:33:36,513 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:33:36,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:36,513 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:36,515 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:33:36,517 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-03-03 14:33:36,610 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 583 statements into 78 equivalence classes. [2025-03-03 14:33:36,670 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 32 check-sat command(s) and asserted 245 of 583 statements. [2025-03-03 14:33:36,670 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 32 check-sat command(s) [2025-03-03 14:33:36,670 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:36,672 INFO L256 TraceCheckSpWp]: Trace formula consists of 559 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-03 14:33:36,682 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:36,767 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 469 proven. 2966 refuted. 0 times theorem prover too weak. 16635 trivial. 0 not checked. [2025-03-03 14:33:36,767 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:39,153 INFO L134 CoverageAnalysis]: Checked inductivity of 20070 backedges. 469 proven. 3043 refuted. 0 times theorem prover too weak. 16558 trivial. 0 not checked. [2025-03-03 14:33:39,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1202581463] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:39,154 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:39,154 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 19] total 21 [2025-03-03 14:33:39,154 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589323574] [2025-03-03 14:33:39,154 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:39,154 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:33:39,154 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:39,155 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:33:39,155 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=308, Unknown=0, NotChecked=0, Total=420 [2025-03-03 14:33:39,155 INFO L87 Difference]: Start difference. First operand 88 states and 133 transitions. Second operand has 21 states, 19 states have (on average 3.3684210526315788) internal successors, (64), 21 states have internal predecessors, (64), 18 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (25), 9 states have call predecessors, (25), 18 states have call successors, (25) [2025-03-03 14:33:39,318 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:39,318 INFO L93 Difference]: Finished difference Result 97 states and 155 transitions. [2025-03-03 14:33:39,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-03 14:33:39,318 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 3.3684210526315788) internal successors, (64), 21 states have internal predecessors, (64), 18 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (25), 9 states have call predecessors, (25), 18 states have call successors, (25) Word has length 583 [2025-03-03 14:33:39,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:39,320 INFO L225 Difference]: With dead ends: 97 [2025-03-03 14:33:39,320 INFO L226 Difference]: Without dead ends: 93 [2025-03-03 14:33:39,320 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1190 GetRequests, 1156 SyntacticMatches, 8 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=238, Invalid=518, Unknown=0, NotChecked=0, Total=756 [2025-03-03 14:33:39,321 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 120 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 166 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 263 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 166 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:39,321 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 102 Invalid, 263 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [166 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:39,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2025-03-03 14:33:39,330 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2025-03-03 14:33:39,333 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 61 states have internal predecessors, (66), 16 states have call successors, (16), 8 states have call predecessors, (16), 13 states have return successors, (69), 23 states have call predecessors, (69), 16 states have call successors, (69) [2025-03-03 14:33:39,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 151 transitions. [2025-03-03 14:33:39,333 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 151 transitions. Word has length 583 [2025-03-03 14:33:39,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:39,334 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 151 transitions. [2025-03-03 14:33:39,334 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 3.3684210526315788) internal successors, (64), 21 states have internal predecessors, (64), 18 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (25), 9 states have call predecessors, (25), 18 states have call successors, (25) [2025-03-03 14:33:39,334 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 151 transitions. [2025-03-03 14:33:39,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 965 [2025-03-03 14:33:39,339 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:39,339 INFO L218 NwaCegarLoop]: trace histogram [141, 141, 114, 70, 70, 70, 70, 70, 70, 70, 44, 27, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:39,345 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-03-03 14:33:39,544 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2025-03-03 14:33:39,544 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:39,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:39,544 INFO L85 PathProgramCache]: Analyzing trace with hash -1772432010, now seen corresponding path program 10 times [2025-03-03 14:33:39,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:39,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [273849906] [2025-03-03 14:33:39,544 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:33:39,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:39,573 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 964 statements into 2 equivalence classes. [2025-03-03 14:33:39,634 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 820 of 964 statements. [2025-03-03 14:33:39,634 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 14:33:39,634 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:40,239 INFO L134 CoverageAnalysis]: Checked inductivity of 55581 backedges. 1293 proven. 6424 refuted. 0 times theorem prover too weak. 47864 trivial. 0 not checked. [2025-03-03 14:33:40,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:40,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [273849906] [2025-03-03 14:33:40,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [273849906] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:40,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [246945882] [2025-03-03 14:33:40,240 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:33:40,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:40,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:40,242 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:33:40,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2025-03-03 14:33:40,374 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 964 statements into 2 equivalence classes. [2025-03-03 14:33:40,490 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 820 of 964 statements. [2025-03-03 14:33:40,490 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 14:33:40,490 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:40,494 INFO L256 TraceCheckSpWp]: Trace formula consists of 1713 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-03 14:33:40,504 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:40,595 INFO L134 CoverageAnalysis]: Checked inductivity of 55581 backedges. 20187 proven. 843 refuted. 0 times theorem prover too weak. 34551 trivial. 0 not checked. [2025-03-03 14:33:40,595 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:43,893 INFO L134 CoverageAnalysis]: Checked inductivity of 55581 backedges. 1383 proven. 7581 refuted. 0 times theorem prover too weak. 46617 trivial. 0 not checked. [2025-03-03 14:33:43,893 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [246945882] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:43,893 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:43,893 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 23] total 28 [2025-03-03 14:33:43,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1717982211] [2025-03-03 14:33:43,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:43,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-03-03 14:33:43,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:43,895 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-03-03 14:33:43,895 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=622, Unknown=0, NotChecked=0, Total=756 [2025-03-03 14:33:43,896 INFO L87 Difference]: Start difference. First operand 93 states and 151 transitions. Second operand has 28 states, 28 states have (on average 3.25) internal successors, (91), 28 states have internal predecessors, (91), 22 states have call successors, (28), 2 states have call predecessors, (28), 12 states have return successors, (37), 13 states have call predecessors, (37), 22 states have call successors, (37) [2025-03-03 14:33:44,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:44,216 INFO L93 Difference]: Finished difference Result 193 states and 378 transitions. [2025-03-03 14:33:44,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2025-03-03 14:33:44,217 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.25) internal successors, (91), 28 states have internal predecessors, (91), 22 states have call successors, (28), 2 states have call predecessors, (28), 12 states have return successors, (37), 13 states have call predecessors, (37), 22 states have call successors, (37) Word has length 964 [2025-03-03 14:33:44,218 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:44,219 INFO L225 Difference]: With dead ends: 193 [2025-03-03 14:33:44,220 INFO L226 Difference]: Without dead ends: 103 [2025-03-03 14:33:44,222 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1968 GetRequests, 1910 SyntacticMatches, 11 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 544 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=604, Invalid=1748, Unknown=0, NotChecked=0, Total=2352 [2025-03-03 14:33:44,222 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 127 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 250 mSolverCounterSat, 128 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 378 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 128 IncrementalHoareTripleChecker+Valid, 250 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:44,223 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [127 Valid, 140 Invalid, 378 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [128 Valid, 250 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:44,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2025-03-03 14:33:44,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 86. [2025-03-03 14:33:44,235 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 60 states have (on average 1.0333333333333334) internal successors, (62), 58 states have internal predecessors, (62), 15 states have call successors, (15), 10 states have call predecessors, (15), 10 states have return successors, (51), 17 states have call predecessors, (51), 15 states have call successors, (51) [2025-03-03 14:33:44,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 128 transitions. [2025-03-03 14:33:44,236 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 128 transitions. Word has length 964 [2025-03-03 14:33:44,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:44,237 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 128 transitions. [2025-03-03 14:33:44,237 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.25) internal successors, (91), 28 states have internal predecessors, (91), 22 states have call successors, (28), 2 states have call predecessors, (28), 12 states have return successors, (37), 13 states have call predecessors, (37), 22 states have call successors, (37) [2025-03-03 14:33:44,237 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 128 transitions. [2025-03-03 14:33:44,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1060 [2025-03-03 14:33:44,244 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:44,245 INFO L218 NwaCegarLoop]: trace histogram [155, 155, 125, 77, 77, 77, 77, 77, 77, 77, 48, 30, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:44,261 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2025-03-03 14:33:44,445 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2025-03-03 14:33:44,445 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:44,446 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:44,446 INFO L85 PathProgramCache]: Analyzing trace with hash -1898637249, now seen corresponding path program 11 times [2025-03-03 14:33:44,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:44,446 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1133439678] [2025-03-03 14:33:44,446 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-03 14:33:44,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:44,464 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1059 statements into 126 equivalence classes. [2025-03-03 14:33:44,563 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 64 check-sat command(s) and asserted 513 of 1059 statements. [2025-03-03 14:33:44,563 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 64 check-sat command(s) [2025-03-03 14:33:44,563 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:45,129 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 5023 proven. 5215 refuted. 0 times theorem prover too weak. 56956 trivial. 0 not checked. [2025-03-03 14:33:45,129 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:45,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1133439678] [2025-03-03 14:33:45,129 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1133439678] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:45,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [982575680] [2025-03-03 14:33:45,130 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-03-03 14:33:45,130 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:45,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:45,131 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:33:45,133 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2025-03-03 14:33:45,290 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 1059 statements into 126 equivalence classes. [2025-03-03 14:33:45,403 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 64 check-sat command(s) and asserted 513 of 1059 statements. [2025-03-03 14:33:45,403 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 64 check-sat command(s) [2025-03-03 14:33:45,403 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:45,406 INFO L256 TraceCheckSpWp]: Trace formula consists of 1143 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-03 14:33:45,418 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:45,518 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 34209 proven. 1768 refuted. 0 times theorem prover too weak. 31217 trivial. 0 not checked. [2025-03-03 14:33:45,519 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:49,175 INFO L134 CoverageAnalysis]: Checked inductivity of 67194 backedges. 4913 proven. 5212 refuted. 0 times theorem prover too weak. 57069 trivial. 0 not checked. [2025-03-03 14:33:49,175 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [982575680] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:49,175 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:49,176 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 16, 25] total 35 [2025-03-03 14:33:49,176 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1667923929] [2025-03-03 14:33:49,176 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:49,177 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-03 14:33:49,177 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:49,177 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-03 14:33:49,178 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=960, Unknown=0, NotChecked=0, Total=1190 [2025-03-03 14:33:49,178 INFO L87 Difference]: Start difference. First operand 86 states and 128 transitions. Second operand has 35 states, 35 states have (on average 3.057142857142857) internal successors, (107), 35 states have internal predecessors, (107), 26 states have call successors, (34), 2 states have call predecessors, (34), 15 states have return successors, (46), 19 states have call predecessors, (46), 26 states have call successors, (46) [2025-03-03 14:33:49,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:49,565 INFO L93 Difference]: Finished difference Result 195 states and 353 transitions. [2025-03-03 14:33:49,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2025-03-03 14:33:49,565 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 3.057142857142857) internal successors, (107), 35 states have internal predecessors, (107), 26 states have call successors, (34), 2 states have call predecessors, (34), 15 states have return successors, (46), 19 states have call predecessors, (46), 26 states have call successors, (46) Word has length 1059 [2025-03-03 14:33:49,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:49,567 INFO L225 Difference]: With dead ends: 195 [2025-03-03 14:33:49,567 INFO L226 Difference]: Without dead ends: 112 [2025-03-03 14:33:49,568 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2169 GetRequests, 2100 SyntacticMatches, 12 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1071 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=833, Invalid=2589, Unknown=0, NotChecked=0, Total=3422 [2025-03-03 14:33:49,569 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 156 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 164 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 156 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 479 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 164 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:49,569 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [156 Valid, 171 Invalid, 479 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [164 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:33:49,569 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2025-03-03 14:33:49,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 98. [2025-03-03 14:33:49,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 69 states have (on average 1.0289855072463767) internal successors, (71), 67 states have internal predecessors, (71), 18 states have call successors, (18), 13 states have call predecessors, (18), 10 states have return successors, (53), 17 states have call predecessors, (53), 18 states have call successors, (53) [2025-03-03 14:33:49,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 142 transitions. [2025-03-03 14:33:49,580 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 142 transitions. Word has length 1059 [2025-03-03 14:33:49,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:49,581 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 142 transitions. [2025-03-03 14:33:49,581 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 3.057142857142857) internal successors, (107), 35 states have internal predecessors, (107), 26 states have call successors, (34), 2 states have call predecessors, (34), 15 states have return successors, (46), 19 states have call predecessors, (46), 26 states have call successors, (46) [2025-03-03 14:33:49,581 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 142 transitions. [2025-03-03 14:33:49,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 815 [2025-03-03 14:33:49,584 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:49,585 INFO L218 NwaCegarLoop]: trace histogram [119, 119, 96, 59, 59, 59, 59, 59, 59, 59, 37, 23, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:49,592 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2025-03-03 14:33:49,785 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2025-03-03 14:33:49,785 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:49,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:49,786 INFO L85 PathProgramCache]: Analyzing trace with hash 1402662446, now seen corresponding path program 12 times [2025-03-03 14:33:49,786 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:49,786 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2065455591] [2025-03-03 14:33:49,786 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-03 14:33:49,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:49,800 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 814 statements into 93 equivalence classes. [2025-03-03 14:33:49,828 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 26 check-sat command(s) and asserted 239 of 814 statements. [2025-03-03 14:33:49,828 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 26 check-sat command(s) [2025-03-03 14:33:49,828 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:49,990 INFO L134 CoverageAnalysis]: Checked inductivity of 39488 backedges. 1358 proven. 3585 refuted. 0 times theorem prover too weak. 34545 trivial. 0 not checked. [2025-03-03 14:33:49,990 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:49,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2065455591] [2025-03-03 14:33:49,990 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2065455591] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:49,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1591685636] [2025-03-03 14:33:49,990 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2025-03-03 14:33:49,990 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:49,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:49,993 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:33:49,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2025-03-03 14:33:50,170 INFO L108 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE partitioned 814 statements into 93 equivalence classes. [2025-03-03 14:33:50,220 INFO L111 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 26 check-sat command(s) and asserted 239 of 814 statements. [2025-03-03 14:33:50,220 INFO L114 AnnotateAndAsserter]: Assert order MIX_INSIDE_OUTSIDE issued 26 check-sat command(s) [2025-03-03 14:33:50,220 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:50,222 INFO L256 TraceCheckSpWp]: Trace formula consists of 549 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-03-03 14:33:50,229 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:50,281 INFO L134 CoverageAnalysis]: Checked inductivity of 39488 backedges. 1358 proven. 3585 refuted. 0 times theorem prover too weak. 34545 trivial. 0 not checked. [2025-03-03 14:33:50,281 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:33:52,979 INFO L134 CoverageAnalysis]: Checked inductivity of 39488 backedges. 1366 proven. 3654 refuted. 0 times theorem prover too weak. 34468 trivial. 0 not checked. [2025-03-03 14:33:52,979 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1591685636] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:33:52,979 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:33:52,979 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 19] total 21 [2025-03-03 14:33:52,979 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1262353541] [2025-03-03 14:33:52,979 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:33:52,980 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2025-03-03 14:33:52,980 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:33:52,981 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2025-03-03 14:33:52,981 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=308, Unknown=0, NotChecked=0, Total=420 [2025-03-03 14:33:52,981 INFO L87 Difference]: Start difference. First operand 98 states and 142 transitions. Second operand has 21 states, 19 states have (on average 3.4210526315789473) internal successors, (65), 21 states have internal predecessors, (65), 17 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 11 states have call predecessors, (26), 17 states have call successors, (26) [2025-03-03 14:33:53,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:33:53,081 INFO L93 Difference]: Finished difference Result 110 states and 170 transitions. [2025-03-03 14:33:53,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-03-03 14:33:53,081 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 3.4210526315789473) internal successors, (65), 21 states have internal predecessors, (65), 17 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 11 states have call predecessors, (26), 17 states have call successors, (26) Word has length 814 [2025-03-03 14:33:53,082 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:33:53,083 INFO L225 Difference]: With dead ends: 110 [2025-03-03 14:33:53,083 INFO L226 Difference]: Without dead ends: 106 [2025-03-03 14:33:53,083 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 1652 GetRequests, 1618 SyntacticMatches, 8 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=238, Invalid=518, Unknown=0, NotChecked=0, Total=756 [2025-03-03 14:33:53,084 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 49 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:33:53,084 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 95 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:33:53,084 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2025-03-03 14:33:53,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 103. [2025-03-03 14:33:53,094 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 72 states have (on average 1.0277777777777777) internal successors, (74), 70 states have internal predecessors, (74), 19 states have call successors, (19), 13 states have call predecessors, (19), 11 states have return successors, (65), 19 states have call predecessors, (65), 19 states have call successors, (65) [2025-03-03 14:33:53,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 158 transitions. [2025-03-03 14:33:53,095 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 158 transitions. Word has length 814 [2025-03-03 14:33:53,096 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:33:53,096 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 158 transitions. [2025-03-03 14:33:53,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 3.4210526315789473) internal successors, (65), 21 states have internal predecessors, (65), 17 states have call successors, (20), 1 states have call predecessors, (20), 9 states have return successors, (26), 11 states have call predecessors, (26), 17 states have call successors, (26) [2025-03-03 14:33:53,096 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 158 transitions. [2025-03-03 14:33:53,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1537 [2025-03-03 14:33:53,106 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:33:53,106 INFO L218 NwaCegarLoop]: trace histogram [225, 225, 182, 112, 112, 112, 112, 112, 112, 112, 70, 43, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:33:53,113 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2025-03-03 14:33:53,307 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2025-03-03 14:33:53,307 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:33:53,307 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:33:53,308 INFO L85 PathProgramCache]: Analyzing trace with hash -110103902, now seen corresponding path program 13 times [2025-03-03 14:33:53,308 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:33:53,308 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1425170541] [2025-03-03 14:33:53,308 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-03 14:33:53,308 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:33:53,329 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1536 statements into 1 equivalence classes. [2025-03-03 14:33:53,516 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1536 of 1536 statements. [2025-03-03 14:33:53,517 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:53,517 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:55,093 INFO L134 CoverageAnalysis]: Checked inductivity of 142135 backedges. 1452 proven. 10624 refuted. 0 times theorem prover too weak. 130059 trivial. 0 not checked. [2025-03-03 14:33:55,094 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:33:55,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1425170541] [2025-03-03 14:33:55,094 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1425170541] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:33:55,094 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [967173982] [2025-03-03 14:33:55,094 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2025-03-03 14:33:55,094 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:33:55,094 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:33:55,096 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:33:55,098 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2025-03-03 14:33:55,313 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 1536 statements into 1 equivalence classes. [2025-03-03 14:33:55,521 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 1536 of 1536 statements. [2025-03-03 14:33:55,521 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 14:33:55,521 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:33:55,529 INFO L256 TraceCheckSpWp]: Trace formula consists of 3429 conjuncts, 22 conjuncts are in the unsatisfiable core [2025-03-03 14:33:55,541 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:33:55,626 INFO L134 CoverageAnalysis]: Checked inductivity of 142135 backedges. 1452 proven. 10624 refuted. 0 times theorem prover too weak. 130059 trivial. 0 not checked. [2025-03-03 14:33:55,626 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:00,854 INFO L134 CoverageAnalysis]: Checked inductivity of 142135 backedges. 1452 proven. 10750 refuted. 0 times theorem prover too weak. 129933 trivial. 0 not checked. [2025-03-03 14:34:00,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [967173982] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:00,855 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:00,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 23] total 25 [2025-03-03 14:34:00,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1925440388] [2025-03-03 14:34:00,855 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:00,856 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-03 14:34:00,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:00,856 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-03 14:34:00,857 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=442, Unknown=0, NotChecked=0, Total=600 [2025-03-03 14:34:00,857 INFO L87 Difference]: Start difference. First operand 103 states and 158 transitions. Second operand has 25 states, 23 states have (on average 3.3043478260869565) internal successors, (76), 25 states have internal predecessors, (76), 22 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (31), 11 states have call predecessors, (31), 22 states have call successors, (31) [2025-03-03 14:34:01,026 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:01,026 INFO L93 Difference]: Finished difference Result 120 states and 211 transitions. [2025-03-03 14:34:01,026 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-03-03 14:34:01,027 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 23 states have (on average 3.3043478260869565) internal successors, (76), 25 states have internal predecessors, (76), 22 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (31), 11 states have call predecessors, (31), 22 states have call successors, (31) Word has length 1536 [2025-03-03 14:34:01,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:01,029 INFO L225 Difference]: With dead ends: 120 [2025-03-03 14:34:01,029 INFO L226 Difference]: Without dead ends: 116 [2025-03-03 14:34:01,030 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3102 GetRequests, 3060 SyntacticMatches, 10 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 281 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=356, Invalid=766, Unknown=0, NotChecked=0, Total=1122 [2025-03-03 14:34:01,031 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 138 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 160 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 278 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 160 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:01,031 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 123 Invalid, 278 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [160 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 14:34:01,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2025-03-03 14:34:01,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 108. [2025-03-03 14:34:01,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 75 states have (on average 1.0266666666666666) internal successors, (77), 73 states have internal predecessors, (77), 20 states have call successors, (20), 13 states have call predecessors, (20), 12 states have return successors, (79), 21 states have call predecessors, (79), 20 states have call successors, (79) [2025-03-03 14:34:01,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 176 transitions. [2025-03-03 14:34:01,064 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 176 transitions. Word has length 1536 [2025-03-03 14:34:01,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:01,066 INFO L471 AbstractCegarLoop]: Abstraction has 108 states and 176 transitions. [2025-03-03 14:34:01,066 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 23 states have (on average 3.3043478260869565) internal successors, (76), 25 states have internal predecessors, (76), 22 states have call successors, (23), 1 states have call predecessors, (23), 11 states have return successors, (31), 11 states have call predecessors, (31), 22 states have call successors, (31) [2025-03-03 14:34:01,066 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 176 transitions. [2025-03-03 14:34:01,087 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2408 [2025-03-03 14:34:01,087 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:01,087 INFO L218 NwaCegarLoop]: trace histogram [353, 353, 285, 176, 176, 176, 176, 176, 176, 176, 109, 68, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:01,097 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2025-03-03 14:34:01,288 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:01,288 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:01,288 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:01,289 INFO L85 PathProgramCache]: Analyzing trace with hash 1104519535, now seen corresponding path program 14 times [2025-03-03 14:34:01,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:01,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1482814753] [2025-03-03 14:34:01,289 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:34:01,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:01,321 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 2407 statements into 2 equivalence classes. [2025-03-03 14:34:01,605 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 2407 of 2407 statements. [2025-03-03 14:34:01,605 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:34:01,605 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:05,714 INFO L134 CoverageAnalysis]: Checked inductivity of 350582 backedges. 2438 proven. 18747 refuted. 0 times theorem prover too weak. 329397 trivial. 0 not checked. [2025-03-03 14:34:05,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:05,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1482814753] [2025-03-03 14:34:05,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1482814753] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:05,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1033384658] [2025-03-03 14:34:05,714 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 14:34:05,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:05,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:05,716 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:05,717 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2025-03-03 14:34:05,997 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 2407 statements into 2 equivalence classes. [2025-03-03 14:34:06,369 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 2407 of 2407 statements. [2025-03-03 14:34:06,369 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 14:34:06,369 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:06,383 INFO L256 TraceCheckSpWp]: Trace formula consists of 5363 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-03 14:34:06,434 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:06,546 INFO L134 CoverageAnalysis]: Checked inductivity of 350582 backedges. 2438 proven. 18747 refuted. 0 times theorem prover too weak. 329397 trivial. 0 not checked. [2025-03-03 14:34:06,546 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:14,313 INFO L134 CoverageAnalysis]: Checked inductivity of 350582 backedges. 2438 proven. 18902 refuted. 0 times theorem prover too weak. 329242 trivial. 0 not checked. [2025-03-03 14:34:14,313 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1033384658] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:14,313 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:14,314 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 25] total 27 [2025-03-03 14:34:14,314 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1433410653] [2025-03-03 14:34:14,314 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:14,316 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2025-03-03 14:34:14,316 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:14,316 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2025-03-03 14:34:14,316 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=184, Invalid=518, Unknown=0, NotChecked=0, Total=702 [2025-03-03 14:34:14,316 INFO L87 Difference]: Start difference. First operand 108 states and 176 transitions. Second operand has 27 states, 25 states have (on average 3.28) internal successors, (82), 27 states have internal predecessors, (82), 24 states have call successors, (25), 1 states have call predecessors, (25), 12 states have return successors, (34), 12 states have call predecessors, (34), 24 states have call successors, (34) [2025-03-03 14:34:14,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:14,585 INFO L93 Difference]: Finished difference Result 117 states and 200 transitions. [2025-03-03 14:34:14,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-03 14:34:14,585 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 3.28) internal successors, (82), 27 states have internal predecessors, (82), 24 states have call successors, (25), 1 states have call predecessors, (25), 12 states have return successors, (34), 12 states have call predecessors, (34), 24 states have call successors, (34) Word has length 2407 [2025-03-03 14:34:14,587 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:14,588 INFO L225 Difference]: With dead ends: 117 [2025-03-03 14:34:14,588 INFO L226 Difference]: Without dead ends: 113 [2025-03-03 14:34:14,589 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4847 GetRequests, 4801 SyntacticMatches, 11 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 342 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=424, Invalid=908, Unknown=0, NotChecked=0, Total=1332 [2025-03-03 14:34:14,589 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 204 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 322 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 220 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 427 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 322 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:14,589 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [220 Valid, 114 Invalid, 427 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [322 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:34:14,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2025-03-03 14:34:14,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 113. [2025-03-03 14:34:14,595 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 78 states have (on average 1.0256410256410255) internal successors, (80), 76 states have internal predecessors, (80), 21 states have call successors, (21), 13 states have call predecessors, (21), 13 states have return successors, (95), 23 states have call predecessors, (95), 21 states have call successors, (95) [2025-03-03 14:34:14,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 196 transitions. [2025-03-03 14:34:14,596 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 196 transitions. Word has length 2407 [2025-03-03 14:34:14,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:14,597 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 196 transitions. [2025-03-03 14:34:14,598 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 3.28) internal successors, (82), 27 states have internal predecessors, (82), 24 states have call successors, (25), 1 states have call predecessors, (25), 12 states have return successors, (34), 12 states have call predecessors, (34), 24 states have call successors, (34) [2025-03-03 14:34:14,598 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 196 transitions. [2025-03-03 14:34:14,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4696 [2025-03-03 14:34:14,671 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:14,672 INFO L218 NwaCegarLoop]: trace histogram [689, 689, 557, 344, 344, 344, 344, 344, 344, 344, 213, 132, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:14,684 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2025-03-03 14:34:14,872 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2025-03-03 14:34:14,872 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:14,873 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:14,873 INFO L85 PathProgramCache]: Analyzing trace with hash -1406486443, now seen corresponding path program 15 times [2025-03-03 14:34:14,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:14,873 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1400720109] [2025-03-03 14:34:14,874 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:34:14,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:14,932 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 4695 statements into 584 equivalence classes. [2025-03-03 14:34:14,976 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 48 check-sat command(s) and asserted 417 of 4695 statements. [2025-03-03 14:34:14,976 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 48 check-sat command(s) [2025-03-03 14:34:14,976 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:15,371 INFO L134 CoverageAnalysis]: Checked inductivity of 1338894 backedges. 4835 proven. 41026 refuted. 0 times theorem prover too weak. 1293033 trivial. 0 not checked. [2025-03-03 14:34:15,372 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 14:34:15,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1400720109] [2025-03-03 14:34:15,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1400720109] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 14:34:15,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1428919523] [2025-03-03 14:34:15,372 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-03 14:34:15,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 14:34:15,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 14:34:15,374 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 14:34:15,376 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2025-03-03 14:34:15,800 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 4695 statements into 584 equivalence classes. [2025-03-03 14:34:15,888 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 48 check-sat command(s) and asserted 417 of 4695 statements. [2025-03-03 14:34:15,888 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 48 check-sat command(s) [2025-03-03 14:34:15,888 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 14:34:15,893 INFO L256 TraceCheckSpWp]: Trace formula consists of 938 conjuncts, 26 conjuncts are in the unsatisfiable core [2025-03-03 14:34:15,921 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 14:34:16,084 INFO L134 CoverageAnalysis]: Checked inductivity of 1338894 backedges. 4835 proven. 41026 refuted. 0 times theorem prover too weak. 1293033 trivial. 0 not checked. [2025-03-03 14:34:16,084 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 14:34:30,202 INFO L134 CoverageAnalysis]: Checked inductivity of 1338894 backedges. 4835 proven. 41213 refuted. 0 times theorem prover too weak. 1292846 trivial. 0 not checked. [2025-03-03 14:34:30,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1428919523] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 14:34:30,203 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 14:34:30,203 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16, 27] total 29 [2025-03-03 14:34:30,203 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1348066927] [2025-03-03 14:34:30,203 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 14:34:30,206 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2025-03-03 14:34:30,207 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 14:34:30,207 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2025-03-03 14:34:30,207 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=212, Invalid=600, Unknown=0, NotChecked=0, Total=812 [2025-03-03 14:34:30,207 INFO L87 Difference]: Start difference. First operand 113 states and 196 transitions. Second operand has 29 states, 27 states have (on average 3.259259259259259) internal successors, (88), 29 states have internal predecessors, (88), 26 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (37), 13 states have call predecessors, (37), 26 states have call successors, (37) [2025-03-03 14:34:30,493 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 14:34:30,493 INFO L93 Difference]: Finished difference Result 122 states and 222 transitions. [2025-03-03 14:34:30,494 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-03-03 14:34:30,494 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 27 states have (on average 3.259259259259259) internal successors, (88), 29 states have internal predecessors, (88), 26 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (37), 13 states have call predecessors, (37), 26 states have call successors, (37) Word has length 4695 [2025-03-03 14:34:30,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 14:34:30,498 INFO L225 Difference]: With dead ends: 122 [2025-03-03 14:34:30,498 INFO L226 Difference]: Without dead ends: 118 [2025-03-03 14:34:30,499 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 9426 GetRequests, 9376 SyntacticMatches, 12 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=498, Invalid=1062, Unknown=0, NotChecked=0, Total=1560 [2025-03-03 14:34:30,499 INFO L435 NwaCegarLoop]: 13 mSDtfsCounter, 270 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 419 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 287 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 539 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 419 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 14:34:30,499 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [287 Valid, 134 Invalid, 539 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [419 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 14:34:30,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2025-03-03 14:34:30,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 118. [2025-03-03 14:34:30,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 81 states have (on average 1.0246913580246915) internal successors, (83), 79 states have internal predecessors, (83), 22 states have call successors, (22), 13 states have call predecessors, (22), 14 states have return successors, (113), 25 states have call predecessors, (113), 22 states have call successors, (113) [2025-03-03 14:34:30,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 218 transitions. [2025-03-03 14:34:30,507 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 218 transitions. Word has length 4695 [2025-03-03 14:34:30,509 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 14:34:30,509 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 218 transitions. [2025-03-03 14:34:30,509 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 27 states have (on average 3.259259259259259) internal successors, (88), 29 states have internal predecessors, (88), 26 states have call successors, (27), 1 states have call predecessors, (27), 13 states have return successors, (37), 13 states have call predecessors, (37), 26 states have call successors, (37) [2025-03-03 14:34:30,509 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 218 transitions. [2025-03-03 14:34:30,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10116 [2025-03-03 14:34:30,877 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 14:34:30,879 INFO L218 NwaCegarLoop]: trace histogram [1485, 1485, 1201, 742, 742, 742, 742, 742, 742, 742, 459, 284, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 14:34:30,887 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2025-03-03 14:34:31,079 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2025-03-03 14:34:31,079 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 14:34:31,080 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 14:34:31,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1703657899, now seen corresponding path program 16 times [2025-03-03 14:34:31,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 14:34:31,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222020964] [2025-03-03 14:34:31,082 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-03-03 14:34:31,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 14:34:31,206 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 10115 statements into 2 equivalence classes. [2025-03-03 14:34:34,759 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) and asserted 8627 of 10115 statements. [2025-03-03 14:34:34,759 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 1 check-sat command(s) [2025-03-03 14:34:34,759 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat