./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c00e63dc Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/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 052aa366c05075bf32d0b6fa176a2f7194f524315c85e0eaee7e4a343f477db5 --- Real Ultimate output --- This is Ultimate 0.3.0-?-c00e63d-m [2025-02-05 15:07:53,174 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-05 15:07:53,212 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-02-05 15:07:53,215 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-05 15:07:53,215 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-05 15:07:53,227 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-05 15:07:53,228 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-05 15:07:53,228 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-05 15:07:53,228 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-05 15:07:53,228 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-05 15:07:53,228 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-05 15:07:53,228 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-05 15:07:53,229 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Use SBE=true [2025-02-05 15:07:53,229 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-05 15:07:53,229 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-05 15:07:53,230 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 15:07:53,230 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-05 15:07:53,230 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-05 15:07:53,231 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-05 15:07:53,231 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-05 15:07:53,231 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-05 15:07:53,231 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-05 15:07:53,231 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-05 15:07:53,231 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-jdk21/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 -> 052aa366c05075bf32d0b6fa176a2f7194f524315c85e0eaee7e4a343f477db5 [2025-02-05 15:07:53,397 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-05 15:07:53,402 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-05 15:07:53,404 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-05 15:07:53,404 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-05 15:07:53,405 INFO L274 PluginConnector]: CDTParser initialized [2025-02-05 15:07:53,405 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c [2025-02-05 15:07:54,489 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/115f969fb/f242b7dcfedc4c448d9e5265cf34ed05/FLAGbdfa46fa3 [2025-02-05 15:07:54,678 INFO L384 CDTParser]: Found 1 translation units. [2025-02-05 15:07:54,678 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c [2025-02-05 15:07:54,697 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/115f969fb/f242b7dcfedc4c448d9e5265cf34ed05/FLAGbdfa46fa3 [2025-02-05 15:07:55,046 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/115f969fb/f242b7dcfedc4c448d9e5265cf34ed05 [2025-02-05 15:07:55,048 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-05 15:07:55,049 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-05 15:07:55,054 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-05 15:07:55,054 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-05 15:07:55,059 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-05 15:07:55,059 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,060 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4aadd3a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55, skipping insertion in model container [2025-02-05 15:07:55,060 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,072 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-05 15:07:55,170 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c[489,502] [2025-02-05 15:07:55,186 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 15:07:55,195 INFO L200 MainTranslator]: Completed pre-run [2025-02-05 15:07:55,202 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound100.c[489,502] [2025-02-05 15:07:55,207 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 15:07:55,217 INFO L204 MainTranslator]: Completed translation [2025-02-05 15:07:55,218 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55 WrapperNode [2025-02-05 15:07:55,218 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-05 15:07:55,219 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-05 15:07:55,219 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-05 15:07:55,219 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-05 15:07:55,223 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,227 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,236 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 54 [2025-02-05 15:07:55,237 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-05 15:07:55,237 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-05 15:07:55,238 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-05 15:07:55,238 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-05 15:07:55,243 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,243 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,248 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,256 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-02-05 15:07:55,257 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,257 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,259 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,260 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,261 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,261 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,265 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-05 15:07:55,265 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-05 15:07:55,265 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-05 15:07:55,265 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-05 15:07:55,266 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (1/1) ... [2025-02-05 15:07:55,271 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 15:07:55,281 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:55,298 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-05 15:07:55,302 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-05 15:07:55,320 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-05 15:07:55,320 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-02-05 15:07:55,320 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-02-05 15:07:55,320 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-05 15:07:55,320 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-05 15:07:55,320 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-05 15:07:55,321 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-02-05 15:07:55,321 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-02-05 15:07:55,370 INFO L257 CfgBuilder]: Building ICFG [2025-02-05 15:07:55,372 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-05 15:07:55,495 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-02-05 15:07:55,495 INFO L308 CfgBuilder]: Performing block encoding [2025-02-05 15:07:55,501 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-05 15:07:55,501 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-05 15:07:55,501 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 03:07:55 BoogieIcfgContainer [2025-02-05 15:07:55,501 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-05 15:07:55,502 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-05 15:07:55,502 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-05 15:07:55,505 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-05 15:07:55,506 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.02 03:07:55" (1/3) ... [2025-02-05 15:07:55,506 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620bbec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 03:07:55, skipping insertion in model container [2025-02-05 15:07:55,506 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 03:07:55" (2/3) ... [2025-02-05 15:07:55,506 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620bbec and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 03:07:55, skipping insertion in model container [2025-02-05 15:07:55,506 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 03:07:55" (3/3) ... [2025-02-05 15:07:55,507 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound100.c [2025-02-05 15:07:55,516 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-05 15:07:55,517 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd-ll_valuebound100.c that has 3 procedures, 32 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-02-05 15:07:55,545 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-05 15:07:55,554 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;@2dce5457, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-05 15:07:55,554 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-02-05 15:07:55,557 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2025-02-05 15:07:55,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-02-05 15:07:55,564 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:55,564 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:55,565 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:55,568 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:55,568 INFO L85 PathProgramCache]: Analyzing trace with hash 1874562101, now seen corresponding path program 1 times [2025-02-05 15:07:55,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:55,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1592945429] [2025-02-05 15:07:55,573 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:55,573 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:55,614 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 15:07:55,623 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 15:07:55,623 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:55,623 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:55,656 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-05 15:07:55,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:55,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1592945429] [2025-02-05 15:07:55,657 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1592945429] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 15:07:55,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [916228070] [2025-02-05 15:07:55,657 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:55,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:55,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:55,662 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:55,662 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-05 15:07:55,688 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 15:07:55,702 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 15:07:55,702 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:55,702 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:55,703 INFO L256 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-02-05 15:07:55,706 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:55,713 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-02-05 15:07:55,713 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:55,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [916228070] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:55,713 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-05 15:07:55,713 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-02-05 15:07:55,715 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921463317] [2025-02-05 15:07:55,715 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:55,717 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-02-05 15:07:55,718 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:55,728 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-02-05 15:07:55,728 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-02-05 15:07:55,730 INFO L87 Difference]: Start difference. First operand has 32 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-02-05 15:07:55,741 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:55,741 INFO L93 Difference]: Finished difference Result 61 states and 97 transitions. [2025-02-05 15:07:55,742 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-02-05 15:07:55,743 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2025-02-05 15:07:55,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:55,746 INFO L225 Difference]: With dead ends: 61 [2025-02-05 15:07:55,746 INFO L226 Difference]: Without dead ends: 28 [2025-02-05 15:07:55,748 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-02-05 15:07:55,750 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:55,750 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:55,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2025-02-05 15:07:55,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2025-02-05 15:07:55,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-02-05 15:07:55,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 38 transitions. [2025-02-05 15:07:55,771 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 38 transitions. Word has length 29 [2025-02-05 15:07:55,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:55,771 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 38 transitions. [2025-02-05 15:07:55,772 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2025-02-05 15:07:55,772 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 38 transitions. [2025-02-05 15:07:55,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2025-02-05 15:07:55,773 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:55,773 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:55,778 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-02-05 15:07:55,977 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2025-02-05 15:07:55,977 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:55,978 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:55,978 INFO L85 PathProgramCache]: Analyzing trace with hash 934835095, now seen corresponding path program 1 times [2025-02-05 15:07:55,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:55,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [221379539] [2025-02-05 15:07:55,978 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:55,978 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:55,984 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 15:07:56,000 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 15:07:56,000 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,000 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:56,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1379486728] [2025-02-05 15:07:56,002 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:56,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:56,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:56,004 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:56,005 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-05 15:07:56,028 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 29 statements into 1 equivalence classes. [2025-02-05 15:07:56,041 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 29 of 29 statements. [2025-02-05 15:07:56,041 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,041 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:56,042 INFO L256 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-05 15:07:56,043 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:56,114 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-02-05 15:07:56,114 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:56,114 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:56,114 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [221379539] [2025-02-05 15:07:56,115 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:56,115 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1379486728] [2025-02-05 15:07:56,115 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1379486728] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:56,115 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 15:07:56,115 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-05 15:07:56,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087964279] [2025-02-05 15:07:56,115 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:56,116 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:07:56,116 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:56,116 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:07:56,116 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-05 15:07:56,117 INFO L87 Difference]: Start difference. First operand 28 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-02-05 15:07:56,165 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:56,165 INFO L93 Difference]: Finished difference Result 44 states and 61 transitions. [2025-02-05 15:07:56,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:07:56,166 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2025-02-05 15:07:56,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:56,170 INFO L225 Difference]: With dead ends: 44 [2025-02-05 15:07:56,170 INFO L226 Difference]: Without dead ends: 42 [2025-02-05 15:07:56,170 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-05 15:07:56,171 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 5 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:56,171 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 121 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:56,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-02-05 15:07:56,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2025-02-05 15:07:56,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 20 states have (on average 1.25) internal successors, (25), 22 states have internal predecessors, (25), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2025-02-05 15:07:56,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 58 transitions. [2025-02-05 15:07:56,182 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 58 transitions. Word has length 29 [2025-02-05 15:07:56,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:56,182 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 58 transitions. [2025-02-05 15:07:56,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2025-02-05 15:07:56,182 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 58 transitions. [2025-02-05 15:07:56,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-02-05 15:07:56,183 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:56,183 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:56,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-02-05 15:07:56,387 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:56,387 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:56,388 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:56,388 INFO L85 PathProgramCache]: Analyzing trace with hash 1488334121, now seen corresponding path program 1 times [2025-02-05 15:07:56,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:56,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [443834035] [2025-02-05 15:07:56,388 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:56,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:56,393 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-02-05 15:07:56,404 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-02-05 15:07:56,404 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,405 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:56,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2082339104] [2025-02-05 15:07:56,407 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:56,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:56,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:56,409 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:56,410 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-05 15:07:56,433 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-02-05 15:07:56,448 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-02-05 15:07:56,448 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,448 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:56,449 INFO L256 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-05 15:07:56,450 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:56,527 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-02-05 15:07:56,527 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:56,527 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:56,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [443834035] [2025-02-05 15:07:56,527 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:56,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2082339104] [2025-02-05 15:07:56,528 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2082339104] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:56,528 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 15:07:56,528 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-05 15:07:56,528 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1350684627] [2025-02-05 15:07:56,528 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:56,528 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:07:56,528 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:56,528 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:07:56,528 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-05 15:07:56,528 INFO L87 Difference]: Start difference. First operand 41 states and 58 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-02-05 15:07:56,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:56,581 INFO L93 Difference]: Finished difference Result 66 states and 98 transitions. [2025-02-05 15:07:56,581 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:07:56,581 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2025-02-05 15:07:56,581 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:56,583 INFO L225 Difference]: With dead ends: 66 [2025-02-05 15:07:56,583 INFO L226 Difference]: Without dead ends: 64 [2025-02-05 15:07:56,584 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-05 15:07:56,584 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:56,585 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 123 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:56,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-02-05 15:07:56,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 57. [2025-02-05 15:07:56,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 31 states have internal predecessors, (38), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2025-02-05 15:07:56,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 83 transitions. [2025-02-05 15:07:56,602 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 83 transitions. Word has length 34 [2025-02-05 15:07:56,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:56,603 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 83 transitions. [2025-02-05 15:07:56,603 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2025-02-05 15:07:56,603 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 83 transitions. [2025-02-05 15:07:56,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-02-05 15:07:56,604 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:56,604 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:56,613 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-05 15:07:56,804 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:56,805 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:56,805 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:56,805 INFO L85 PathProgramCache]: Analyzing trace with hash -144013545, now seen corresponding path program 1 times [2025-02-05 15:07:56,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:56,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2113835450] [2025-02-05 15:07:56,806 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:56,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:56,814 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-02-05 15:07:56,826 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-02-05 15:07:56,827 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,827 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:56,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1771704995] [2025-02-05 15:07:56,828 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:56,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:56,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:56,830 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:56,832 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-02-05 15:07:56,866 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 39 statements into 1 equivalence classes. [2025-02-05 15:07:56,881 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 39 of 39 statements. [2025-02-05 15:07:56,881 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:56,881 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:56,883 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-02-05 15:07:56,884 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:56,932 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-02-05 15:07:56,932 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:56,933 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:56,933 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2113835450] [2025-02-05 15:07:56,933 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:56,933 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1771704995] [2025-02-05 15:07:56,933 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1771704995] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:56,933 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 15:07:56,933 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-05 15:07:56,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [942887555] [2025-02-05 15:07:56,933 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:56,933 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:07:56,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:56,934 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:07:56,934 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-05 15:07:56,934 INFO L87 Difference]: Start difference. First operand 57 states and 83 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-02-05 15:07:56,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:56,981 INFO L93 Difference]: Finished difference Result 64 states and 89 transitions. [2025-02-05 15:07:56,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:07:56,981 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2025-02-05 15:07:56,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:56,982 INFO L225 Difference]: With dead ends: 64 [2025-02-05 15:07:56,982 INFO L226 Difference]: Without dead ends: 60 [2025-02-05 15:07:56,982 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-05 15:07:56,982 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:56,983 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 122 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:56,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2025-02-05 15:07:56,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2025-02-05 15:07:56,992 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 32 states have (on average 1.28125) internal successors, (41), 34 states have internal predecessors, (41), 22 states have call successors, (22), 5 states have call predecessors, (22), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2025-02-05 15:07:56,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 83 transitions. [2025-02-05 15:07:56,993 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 83 transitions. Word has length 39 [2025-02-05 15:07:56,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:56,993 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 83 transitions. [2025-02-05 15:07:56,993 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2025-02-05 15:07:56,993 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 83 transitions. [2025-02-05 15:07:56,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2025-02-05 15:07:56,994 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:56,994 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:57,002 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-02-05 15:07:57,194 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:57,195 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:57,195 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:57,195 INFO L85 PathProgramCache]: Analyzing trace with hash -252058226, now seen corresponding path program 1 times [2025-02-05 15:07:57,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:57,195 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2136310091] [2025-02-05 15:07:57,195 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:57,195 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:57,205 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-02-05 15:07:57,217 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-02-05 15:07:57,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:57,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:57,353 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-02-05 15:07:57,353 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:57,353 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2136310091] [2025-02-05 15:07:57,353 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2136310091] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:57,353 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 15:07:57,353 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-05 15:07:57,353 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032907243] [2025-02-05 15:07:57,353 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:57,354 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:07:57,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:57,354 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:07:57,354 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-05 15:07:57,354 INFO L87 Difference]: Start difference. First operand 60 states and 83 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2025-02-05 15:07:57,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:57,383 INFO L93 Difference]: Finished difference Result 66 states and 88 transitions. [2025-02-05 15:07:57,383 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:07:57,384 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2025-02-05 15:07:57,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:57,384 INFO L225 Difference]: With dead ends: 66 [2025-02-05 15:07:57,384 INFO L226 Difference]: Without dead ends: 64 [2025-02-05 15:07:57,385 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-05 15:07:57,385 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:57,385 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 132 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:57,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2025-02-05 15:07:57,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2025-02-05 15:07:57,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 37 states have internal predecessors, (44), 22 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2025-02-05 15:07:57,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2025-02-05 15:07:57,392 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 45 [2025-02-05 15:07:57,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:57,392 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2025-02-05 15:07:57,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2025-02-05 15:07:57,392 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2025-02-05 15:07:57,393 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-02-05 15:07:57,393 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:57,393 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:57,393 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-02-05 15:07:57,393 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:57,393 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:57,394 INFO L85 PathProgramCache]: Analyzing trace with hash -1784111281, now seen corresponding path program 1 times [2025-02-05 15:07:57,394 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:57,394 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1551871982] [2025-02-05 15:07:57,394 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:57,394 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:57,398 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-02-05 15:07:57,411 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-02-05 15:07:57,411 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:57,411 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:57,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [618279310] [2025-02-05 15:07:57,412 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:57,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:57,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:57,414 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:57,417 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-02-05 15:07:57,437 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-02-05 15:07:57,449 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-02-05 15:07:57,449 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:57,449 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:57,450 INFO L256 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-05 15:07:57,451 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:57,571 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2025-02-05 15:07:57,571 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:57,572 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:57,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1551871982] [2025-02-05 15:07:57,572 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:57,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [618279310] [2025-02-05 15:07:57,572 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [618279310] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:57,572 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 15:07:57,572 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-02-05 15:07:57,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1078206133] [2025-02-05 15:07:57,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:57,573 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:07:57,573 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:57,573 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:07:57,573 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-02-05 15:07:57,574 INFO L87 Difference]: Start difference. First operand 64 states and 86 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-02-05 15:07:57,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:57,616 INFO L93 Difference]: Finished difference Result 80 states and 104 transitions. [2025-02-05 15:07:57,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:07:57,616 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2025-02-05 15:07:57,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:57,617 INFO L225 Difference]: With dead ends: 80 [2025-02-05 15:07:57,617 INFO L226 Difference]: Without dead ends: 78 [2025-02-05 15:07:57,618 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-02-05 15:07:57,619 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:57,619 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 121 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:07:57,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2025-02-05 15:07:57,629 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 75. [2025-02-05 15:07:57,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 44 states have internal predecessors, (50), 25 states have call successors, (25), 8 states have call predecessors, (25), 8 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2025-02-05 15:07:57,631 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2025-02-05 15:07:57,633 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 47 [2025-02-05 15:07:57,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:57,633 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2025-02-05 15:07:57,633 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-02-05 15:07:57,633 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2025-02-05 15:07:57,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-02-05 15:07:57,633 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:57,634 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:57,644 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-02-05 15:07:57,834 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:57,834 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:57,835 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:57,835 INFO L85 PathProgramCache]: Analyzing trace with hash -1193732526, now seen corresponding path program 1 times [2025-02-05 15:07:57,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:57,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [765409366] [2025-02-05 15:07:57,836 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:57,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:57,844 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-02-05 15:07:57,853 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-02-05 15:07:57,853 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:57,853 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:58,061 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-02-05 15:07:58,062 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:58,062 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [765409366] [2025-02-05 15:07:58,062 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [765409366] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 15:07:58,062 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1447366166] [2025-02-05 15:07:58,062 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:58,062 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:58,062 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:58,064 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:58,066 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-02-05 15:07:58,088 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 50 statements into 1 equivalence classes. [2025-02-05 15:07:58,100 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 50 of 50 statements. [2025-02-05 15:07:58,100 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:58,100 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:58,101 INFO L256 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-05 15:07:58,102 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:58,171 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-02-05 15:07:58,171 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 15:07:58,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1447366166] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 15:07:58,171 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-05 15:07:58,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2025-02-05 15:07:58,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [857379353] [2025-02-05 15:07:58,171 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:07:58,172 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-05 15:07:58,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:58,172 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-05 15:07:58,172 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-02-05 15:07:58,173 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-02-05 15:07:58,284 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:58,285 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2025-02-05 15:07:58,285 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-02-05 15:07:58,285 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2025-02-05 15:07:58,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:58,286 INFO L225 Difference]: With dead ends: 88 [2025-02-05 15:07:58,286 INFO L226 Difference]: Without dead ends: 84 [2025-02-05 15:07:58,287 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2025-02-05 15:07:58,287 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:58,287 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 147 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-05 15:07:58,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2025-02-05 15:07:58,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 83. [2025-02-05 15:07:58,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 47 states have (on average 1.1702127659574468) internal successors, (55), 50 states have internal predecessors, (55), 25 states have call successors, (25), 10 states have call predecessors, (25), 10 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2025-02-05 15:07:58,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 103 transitions. [2025-02-05 15:07:58,295 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 103 transitions. Word has length 50 [2025-02-05 15:07:58,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:58,296 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 103 transitions. [2025-02-05 15:07:58,296 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2025-02-05 15:07:58,296 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 103 transitions. [2025-02-05 15:07:58,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2025-02-05 15:07:58,296 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:58,296 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:58,311 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-02-05 15:07:58,496 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2025-02-05 15:07:58,497 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:58,497 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:58,497 INFO L85 PathProgramCache]: Analyzing trace with hash 910156208, now seen corresponding path program 1 times [2025-02-05 15:07:58,497 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:58,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [747331134] [2025-02-05 15:07:58,497 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:58,497 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:58,504 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-02-05 15:07:58,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-02-05 15:07:58,512 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:58,512 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:58,513 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1938203590] [2025-02-05 15:07:58,513 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:07:58,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:58,513 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:58,517 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:58,520 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-02-05 15:07:58,540 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 52 statements into 1 equivalence classes. [2025-02-05 15:07:58,554 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 52 of 52 statements. [2025-02-05 15:07:58,554 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:07:58,554 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:58,555 INFO L256 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 32 conjuncts are in the unsatisfiable core [2025-02-05 15:07:58,556 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:58,776 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 17 proven. 6 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-02-05 15:07:58,776 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 15:07:58,920 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-02-05 15:07:58,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:58,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [747331134] [2025-02-05 15:07:58,920 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:58,920 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1938203590] [2025-02-05 15:07:58,920 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1938203590] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 15:07:58,920 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 15:07:58,920 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2025-02-05 15:07:58,921 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [204067150] [2025-02-05 15:07:58,921 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 15:07:58,921 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-02-05 15:07:58,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:58,921 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-02-05 15:07:58,921 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2025-02-05 15:07:58,922 INFO L87 Difference]: Start difference. First operand 83 states and 103 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2025-02-05 15:07:59,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:07:59,307 INFO L93 Difference]: Finished difference Result 133 states and 183 transitions. [2025-02-05 15:07:59,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-02-05 15:07:59,308 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) Word has length 52 [2025-02-05 15:07:59,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:07:59,310 INFO L225 Difference]: With dead ends: 133 [2025-02-05 15:07:59,310 INFO L226 Difference]: Without dead ends: 131 [2025-02-05 15:07:59,310 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 90 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2025-02-05 15:07:59,310 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 58 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 179 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 237 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 179 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-05 15:07:59,310 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 212 Invalid, 237 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 179 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-05 15:07:59,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2025-02-05 15:07:59,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 109. [2025-02-05 15:07:59,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 62 states have (on average 1.2258064516129032) internal successors, (76), 65 states have internal predecessors, (76), 34 states have call successors, (34), 12 states have call predecessors, (34), 12 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2025-02-05 15:07:59,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 142 transitions. [2025-02-05 15:07:59,337 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 142 transitions. Word has length 52 [2025-02-05 15:07:59,338 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:07:59,338 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 142 transitions. [2025-02-05 15:07:59,338 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 7 states have call predecessors, (15), 6 states have call successors, (15) [2025-02-05 15:07:59,338 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 142 transitions. [2025-02-05 15:07:59,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2025-02-05 15:07:59,338 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:07:59,339 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:07:59,344 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2025-02-05 15:07:59,543 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:59,543 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:07:59,543 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:07:59,544 INFO L85 PathProgramCache]: Analyzing trace with hash 398552271, now seen corresponding path program 2 times [2025-02-05 15:07:59,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:07:59,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1324849613] [2025-02-05 15:07:59,544 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 15:07:59,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:07:59,548 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 57 statements into 2 equivalence classes. [2025-02-05 15:07:59,559 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 57 of 57 statements. [2025-02-05 15:07:59,559 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 15:07:59,559 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:07:59,560 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1393870858] [2025-02-05 15:07:59,560 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 15:07:59,560 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:07:59,560 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:07:59,564 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:07:59,567 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-02-05 15:07:59,584 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 57 statements into 2 equivalence classes. [2025-02-05 15:07:59,598 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 57 of 57 statements. [2025-02-05 15:07:59,598 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 15:07:59,598 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:07:59,599 INFO L256 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-02-05 15:07:59,600 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:07:59,715 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-02-05 15:07:59,715 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 15:07:59,781 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-02-05 15:07:59,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:07:59,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1324849613] [2025-02-05 15:07:59,782 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:07:59,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1393870858] [2025-02-05 15:07:59,782 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1393870858] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 15:07:59,782 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 15:07:59,782 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2025-02-05 15:07:59,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [116768375] [2025-02-05 15:07:59,782 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 15:07:59,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-02-05 15:07:59,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:07:59,783 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-02-05 15:07:59,783 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-02-05 15:07:59,783 INFO L87 Difference]: Start difference. First operand 109 states and 142 transitions. Second operand has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2025-02-05 15:08:00,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:08:00,013 INFO L93 Difference]: Finished difference Result 122 states and 160 transitions. [2025-02-05 15:08:00,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-02-05 15:08:00,014 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 57 [2025-02-05 15:08:00,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:08:00,014 INFO L225 Difference]: With dead ends: 122 [2025-02-05 15:08:00,015 INFO L226 Difference]: Without dead ends: 104 [2025-02-05 15:08:00,016 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 104 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2025-02-05 15:08:00,017 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 11 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 114 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-02-05 15:08:00,018 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 156 Invalid, 114 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-02-05 15:08:00,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2025-02-05 15:08:00,038 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 101. [2025-02-05 15:08:00,038 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 59 states have (on average 1.2033898305084745) internal successors, (71), 61 states have internal predecessors, (71), 30 states have call successors, (30), 11 states have call predecessors, (30), 11 states have return successors, (28), 28 states have call predecessors, (28), 28 states have call successors, (28) [2025-02-05 15:08:00,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 129 transitions. [2025-02-05 15:08:00,040 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 129 transitions. Word has length 57 [2025-02-05 15:08:00,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:08:00,040 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 129 transitions. [2025-02-05 15:08:00,040 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.75) internal successors, (22), 7 states have internal predecessors, (22), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2025-02-05 15:08:00,040 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 129 transitions. [2025-02-05 15:08:00,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2025-02-05 15:08:00,042 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:08:00,043 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:08:00,050 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2025-02-05 15:08:00,248 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:08:00,248 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:08:00,248 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:08:00,249 INFO L85 PathProgramCache]: Analyzing trace with hash -864502232, now seen corresponding path program 1 times [2025-02-05 15:08:00,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:08:00,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399088269] [2025-02-05 15:08:00,249 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:08:00,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:08:00,252 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-02-05 15:08:00,265 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-02-05 15:08:00,265 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:08:00,265 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 15:08:00,266 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1597747459] [2025-02-05 15:08:00,266 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:08:00,266 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:08:00,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:08:00,268 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:08:00,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2025-02-05 15:08:00,290 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 65 statements into 1 equivalence classes. [2025-02-05 15:08:00,305 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 65 of 65 statements. [2025-02-05 15:08:00,305 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:08:00,305 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:08:00,306 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-02-05 15:08:00,307 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:08:00,422 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-02-05 15:08:00,423 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 15:08:00,489 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2025-02-05 15:08:00,489 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:08:00,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1399088269] [2025-02-05 15:08:00,489 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 15:08:00,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1597747459] [2025-02-05 15:08:00,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1597747459] provided 1 perfect and 1 imperfect interpolant sequences [2025-02-05 15:08:00,489 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-02-05 15:08:00,489 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2025-02-05 15:08:00,489 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1208990498] [2025-02-05 15:08:00,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 15:08:00,490 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-02-05 15:08:00,490 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:08:00,490 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-02-05 15:08:00,490 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-02-05 15:08:00,490 INFO L87 Difference]: Start difference. First operand 101 states and 129 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-02-05 15:08:00,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:08:00,530 INFO L93 Difference]: Finished difference Result 107 states and 134 transitions. [2025-02-05 15:08:00,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 15:08:00,530 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 65 [2025-02-05 15:08:00,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:08:00,531 INFO L225 Difference]: With dead ends: 107 [2025-02-05 15:08:00,531 INFO L226 Difference]: Without dead ends: 102 [2025-02-05 15:08:00,531 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2025-02-05 15:08:00,532 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 4 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:08:00,532 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 109 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:08:00,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2025-02-05 15:08:00,548 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 100. [2025-02-05 15:08:00,548 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 61 states have (on average 1.180327868852459) internal successors, (72), 61 states have internal predecessors, (72), 27 states have call successors, (27), 12 states have call predecessors, (27), 11 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2025-02-05 15:08:00,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 125 transitions. [2025-02-05 15:08:00,549 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 125 transitions. Word has length 65 [2025-02-05 15:08:00,549 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:08:00,549 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 125 transitions. [2025-02-05 15:08:00,549 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-02-05 15:08:00,550 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 125 transitions. [2025-02-05 15:08:00,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2025-02-05 15:08:00,550 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 15:08:00,550 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:08:00,558 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2025-02-05 15:08:00,750 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:08:00,751 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 15:08:00,752 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 15:08:00,752 INFO L85 PathProgramCache]: Analyzing trace with hash 1578032345, now seen corresponding path program 1 times [2025-02-05 15:08:00,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 15:08:00,753 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069155273] [2025-02-05 15:08:00,753 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:08:00,753 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 15:08:00,756 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 68 statements into 1 equivalence classes. [2025-02-05 15:08:00,768 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 68 of 68 statements. [2025-02-05 15:08:00,769 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:08:00,769 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:08:00,929 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2025-02-05 15:08:00,929 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 15:08:00,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069155273] [2025-02-05 15:08:00,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2069155273] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 15:08:00,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [418546907] [2025-02-05 15:08:00,929 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 15:08:00,929 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:08:00,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 15:08:00,931 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 15:08:00,933 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2025-02-05 15:08:00,955 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 68 statements into 1 equivalence classes. [2025-02-05 15:08:00,969 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 68 of 68 statements. [2025-02-05 15:08:00,969 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 15:08:00,970 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 15:08:00,970 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-05 15:08:00,972 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 15:08:01,015 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2025-02-05 15:08:01,015 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 15:08:01,091 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2025-02-05 15:08:01,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [418546907] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 15:08:01,091 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-05 15:08:01,091 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2025-02-05 15:08:01,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [345644352] [2025-02-05 15:08:01,091 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-05 15:08:01,092 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-02-05 15:08:01,092 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 15:08:01,092 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-02-05 15:08:01,092 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-02-05 15:08:01,092 INFO L87 Difference]: Start difference. First operand 100 states and 125 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-02-05 15:08:01,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 15:08:01,177 INFO L93 Difference]: Finished difference Result 111 states and 136 transitions. [2025-02-05 15:08:01,178 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-02-05 15:08:01,178 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 68 [2025-02-05 15:08:01,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 15:08:01,179 INFO L225 Difference]: With dead ends: 111 [2025-02-05 15:08:01,179 INFO L226 Difference]: Without dead ends: 0 [2025-02-05 15:08:01,180 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 132 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2025-02-05 15:08:01,181 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 11 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 88 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 15:08:01,181 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 88 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 15:08:01,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-02-05 15:08:01,182 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-02-05 15:08:01,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 15:08:01,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-02-05 15:08:01,182 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 68 [2025-02-05 15:08:01,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 15:08:01,182 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-02-05 15:08:01,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2025-02-05 15:08:01,182 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-02-05 15:08:01,183 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-02-05 15:08:01,184 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-02-05 15:08:01,190 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2025-02-05 15:08:01,385 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 15:08:01,388 INFO L422 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 15:08:01,389 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-02-05 15:08:10,958 WARN L286 SmtUtils]: Spent 7.19s on a formula simplification. DAG size of input: 67 DAG size of output: 34 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2025-02-05 15:08:17,708 WARN L286 SmtUtils]: Spent 6.47s on a formula simplification. DAG size of input: 76 DAG size of output: 36 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2025-02-05 15:08:17,711 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-02-05 15:08:17,720 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.02 03:08:17 BoogieIcfgContainer [2025-02-05 15:08:17,720 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-02-05 15:08:17,720 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-02-05 15:08:17,720 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-02-05 15:08:17,720 INFO L274 PluginConnector]: Witness Printer initialized [2025-02-05 15:08:17,721 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 03:07:55" (3/4) ... [2025-02-05 15:08:17,722 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-02-05 15:08:17,726 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2025-02-05 15:08:17,726 INFO L385 IcfgBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-02-05 15:08:17,728 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2025-02-05 15:08:17,728 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-02-05 15:08:17,728 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-02-05 15:08:17,728 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-02-05 15:08:17,776 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-02-05 15:08:17,776 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.yml [2025-02-05 15:08:17,776 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-02-05 15:08:17,777 INFO L158 Benchmark]: Toolchain (without parser) took 22727.65ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 115.2MB in the beginning and 137.2MB in the end (delta: -22.0MB). Peak memory consumption was 120.9MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,777 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-02-05 15:08:17,777 INFO L158 Benchmark]: CACSL2BoogieTranslator took 164.34ms. Allocated memory is still 142.6MB. Free memory was 114.5MB in the beginning and 103.4MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,777 INFO L158 Benchmark]: Boogie Procedure Inliner took 18.50ms. Allocated memory is still 142.6MB. Free memory was 103.4MB in the beginning and 102.6MB in the end (delta: 757.7kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-05 15:08:17,777 INFO L158 Benchmark]: Boogie Preprocessor took 27.44ms. Allocated memory is still 142.6MB. Free memory was 102.6MB in the beginning and 101.0MB in the end (delta: 1.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,778 INFO L158 Benchmark]: IcfgBuilder took 235.86ms. Allocated memory is still 142.6MB. Free memory was 101.0MB in the beginning and 88.9MB in the end (delta: 12.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,778 INFO L158 Benchmark]: TraceAbstraction took 22217.57ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 88.9MB in the beginning and 142.3MB in the end (delta: -53.5MB). Peak memory consumption was 138.5MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,778 INFO L158 Benchmark]: Witness Printer took 56.11ms. Allocated memory is still 285.2MB. Free memory was 142.3MB in the beginning and 137.2MB in the end (delta: 5.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 15:08:17,779 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18ms. Allocated memory is still 201.3MB. Free memory is still 127.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 164.34ms. Allocated memory is still 142.6MB. Free memory was 114.5MB in the beginning and 103.4MB in the end (delta: 11.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 18.50ms. Allocated memory is still 142.6MB. Free memory was 103.4MB in the beginning and 102.6MB in the end (delta: 757.7kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 27.44ms. Allocated memory is still 142.6MB. Free memory was 102.6MB in the beginning and 101.0MB in the end (delta: 1.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 235.86ms. Allocated memory is still 142.6MB. Free memory was 101.0MB in the beginning and 88.9MB in the end (delta: 12.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 22217.57ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 88.9MB in the beginning and 142.3MB in the end (delta: -53.5MB). Peak memory consumption was 138.5MB. Max. memory is 16.1GB. * Witness Printer took 56.11ms. Allocated memory is still 285.2MB. Free memory was 142.3MB in the beginning and 137.2MB in the end (delta: 5.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 5.9s, OverallIterations: 11, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 143 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 114 mSDsluCounter, 1373 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1004 mSDsCounter, 104 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 553 IncrementalHoareTripleChecker+Invalid, 657 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 104 mSolverCounterUnsat, 369 mSDtfsCounter, 553 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 742 GetRequests, 661 SyntacticMatches, 8 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=109occurred in iteration=8, InterpolantAutomatonStates: 67, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 11 MinimizatonAttempts, 39 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.8s InterpolantComputationTime, 985 NumberOfCodeBlocks, 985 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 886 ConstructedInterpolants, 0 QuantifiedInterpolants, 2471 SizeOfPredicates, 18 NumberOfNonLiveVariables, 1176 ConjunctsInSsa, 135 ConjunctsInUnsatCore, 18 InterpolantComputations, 8 PerfectInterpolantSequences, 1134/1195 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 35]: Location Invariant Derived location invariant: (((((((__int128) p * s) == (((__int128) q * r) + 1)) && (1 <= y)) && ((((__int128) s * y) + ((__int128) q * x)) == b)) && (((((__int128) r * y) + b) + ((__int128) p * x)) == ((a + ((__int128) s * y)) + ((__int128) q * x)))) && (y <= 100)) RESULT: Ultimate proved your program to be correct! [2025-02-05 15:08:17,791 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE