./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 551b0097 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_valuebound10.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 3d9847fe213bf8df5d23c53d2bc8b53fb384c85820b87c09591484702dabefc3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 03:17:10,202 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 03:17:10,252 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-09 03:17:10,257 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 03:17:10,260 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 03:17:10,283 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 03:17:10,283 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 03:17:10,284 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 03:17:10,284 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 03:17:10,284 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 03:17:10,284 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 03:17:10,284 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 03:17:10,285 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 03:17:10,286 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 03:17:10,287 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:17:10,287 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 03:17:10,287 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:17:10,288 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 03:17:10,288 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 03:17:10,288 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 -> 3d9847fe213bf8df5d23c53d2bc8b53fb384c85820b87c09591484702dabefc3 [2025-01-09 03:17:10,524 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 03:17:10,529 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 03:17:10,532 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 03:17:10,533 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 03:17:10,533 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 03:17:10,534 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_valuebound10.c [2025-01-09 03:17:11,651 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d4e1b5d20/3a8b225872e34456a71ae84ebaca3cd5/FLAG2df946211 [2025-01-09 03:17:11,889 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 03:17:11,890 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound10.c [2025-01-09 03:17:11,896 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d4e1b5d20/3a8b225872e34456a71ae84ebaca3cd5/FLAG2df946211 [2025-01-09 03:17:12,226 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d4e1b5d20/3a8b225872e34456a71ae84ebaca3cd5 [2025-01-09 03:17:12,228 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 03:17:12,230 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 03:17:12,232 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 03:17:12,232 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 03:17:12,235 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 03:17:12,236 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,237 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@17c5f70e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12, skipping insertion in model container [2025-01-09 03:17:12,237 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,249 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 03:17:12,351 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_valuebound10.c[489,502] [2025-01-09 03:17:12,370 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 03:17:12,376 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 03:17:12,386 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_valuebound10.c[489,502] [2025-01-09 03:17:12,397 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 03:17:12,408 INFO L204 MainTranslator]: Completed translation [2025-01-09 03:17:12,409 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12 WrapperNode [2025-01-09 03:17:12,410 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 03:17:12,411 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 03:17:12,411 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 03:17:12,411 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 03:17:12,417 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,421 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,434 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 54 [2025-01-09 03:17:12,434 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 03:17:12,435 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 03:17:12,435 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 03:17:12,436 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 03:17:12,442 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,443 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,443 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,454 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-01-09 03:17:12,454 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,454 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,456 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,458 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,461 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,463 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,464 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,465 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 03:17:12,465 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 03:17:12,466 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 03:17:12,466 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 03:17:12,470 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (1/1) ... [2025-01-09 03:17:12,474 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:17:12,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:12,498 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-01-09 03:17:12,502 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-01-09 03:17:12,521 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 03:17:12,521 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2025-01-09 03:17:12,521 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2025-01-09 03:17:12,522 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 03:17:12,522 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 03:17:12,522 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 03:17:12,522 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 03:17:12,522 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 03:17:12,566 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 03:17:12,567 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 03:17:12,687 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-01-09 03:17:12,687 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 03:17:12,696 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 03:17:12,696 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2025-01-09 03:17:12,696 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:17:12 BoogieIcfgContainer [2025-01-09 03:17:12,696 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 03:17:12,699 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 03:17:12,699 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 03:17:12,703 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 03:17:12,703 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 03:17:12" (1/3) ... [2025-01-09 03:17:12,704 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c233584 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 03:17:12, skipping insertion in model container [2025-01-09 03:17:12,704 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:17:12" (2/3) ... [2025-01-09 03:17:12,704 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c233584 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 03:17:12, skipping insertion in model container [2025-01-09 03:17:12,704 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:17:12" (3/3) ... [2025-01-09 03:17:12,705 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound10.c [2025-01-09 03:17:12,715 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 03:17:12,716 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd-ll_valuebound10.c that has 3 procedures, 31 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-01-09 03:17:12,757 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 03:17:12,764 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;@30896f8b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 03:17:12,765 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 03:17:12,768 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 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-01-09 03:17:12,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-01-09 03:17:12,775 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:12,775 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:12,775 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:12,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:12,779 INFO L85 PathProgramCache]: Analyzing trace with hash 1187396966, now seen corresponding path program 1 times [2025-01-09 03:17:12,784 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:12,786 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1597798135] [2025-01-09 03:17:12,787 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:12,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:12,833 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-01-09 03:17:12,842 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-01-09 03:17:12,843 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:12,843 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:12,895 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-09 03:17:12,895 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:12,895 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1597798135] [2025-01-09 03:17:12,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1597798135] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 03:17:12,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [169010752] [2025-01-09 03:17:12,896 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:12,896 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:12,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:12,898 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-01-09 03:17:12,901 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-01-09 03:17:12,933 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-01-09 03:17:12,958 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-01-09 03:17:12,959 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:12,959 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:12,962 INFO L256 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 1 conjuncts are in the unsatisfiable core [2025-01-09 03:17:12,965 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:12,973 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2025-01-09 03:17:12,974 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:12,974 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [169010752] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:12,974 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 03:17:12,974 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2025-01-09 03:17:12,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [615886577] [2025-01-09 03:17:12,976 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:12,978 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 03:17:12,979 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:12,993 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 03:17:12,993 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 03:17:12,994 INFO L87 Difference]: Start difference. First operand has 31 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 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.0) internal successors, (12), 2 states have internal predecessors, (12), 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-01-09 03:17:13,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:13,007 INFO L93 Difference]: Finished difference Result 59 states and 95 transitions. [2025-01-09 03:17:13,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 03:17:13,009 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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 28 [2025-01-09 03:17:13,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:13,013 INFO L225 Difference]: With dead ends: 59 [2025-01-09 03:17:13,013 INFO L226 Difference]: Without dead ends: 27 [2025-01-09 03:17:13,015 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 29 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-01-09 03:17:13,016 INFO L435 NwaCegarLoop]: 41 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, 41 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-01-09 03:17:13,017 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:13,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-01-09 03:17:13,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-01-09 03:17:13,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 14 states have internal predecessors, (16), 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-01-09 03:17:13,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 37 transitions. [2025-01-09 03:17:13,043 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 37 transitions. Word has length 28 [2025-01-09 03:17:13,044 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:13,044 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 37 transitions. [2025-01-09 03:17:13,044 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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-01-09 03:17:13,044 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 37 transitions. [2025-01-09 03:17:13,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-01-09 03:17:13,045 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:13,045 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:13,052 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:13,245 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-01-09 03:17:13,246 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:13,246 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:13,246 INFO L85 PathProgramCache]: Analyzing trace with hash 1958053410, now seen corresponding path program 1 times [2025-01-09 03:17:13,246 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:13,246 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1276707574] [2025-01-09 03:17:13,246 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:13,246 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:13,253 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-01-09 03:17:13,279 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-01-09 03:17:13,281 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:13,281 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:13,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1935458874] [2025-01-09 03:17:13,282 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:13,283 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:13,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:13,285 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-01-09 03:17:13,287 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-01-09 03:17:13,319 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-01-09 03:17:13,333 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-01-09 03:17:13,334 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:13,334 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:13,334 INFO L256 TraceCheckSpWp]: Trace formula consists of 82 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-01-09 03:17:13,336 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:13,408 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-01-09 03:17:13,408 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:13,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:13,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1276707574] [2025-01-09 03:17:13,409 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:13,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1935458874] [2025-01-09 03:17:13,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1935458874] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:13,409 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:17:13,409 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:17:13,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [191250805] [2025-01-09 03:17:13,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:13,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:13,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:13,411 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:13,411 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:17:13,411 INFO L87 Difference]: Start difference. First operand 27 states and 37 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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-01-09 03:17:13,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:13,466 INFO L93 Difference]: Finished difference Result 42 states and 59 transitions. [2025-01-09 03:17:13,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:13,467 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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 28 [2025-01-09 03:17:13,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:13,468 INFO L225 Difference]: With dead ends: 42 [2025-01-09 03:17:13,468 INFO L226 Difference]: Without dead ends: 40 [2025-01-09 03:17:13,468 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 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-01-09 03:17:13,468 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 5 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 117 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-01-09 03:17:13,469 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 117 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:13,471 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-01-09 03:17:13,479 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2025-01-09 03:17:13,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 18 states have (on average 1.2777777777777777) internal successors, (23), 20 states have internal predecessors, (23), 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-01-09 03:17:13,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 56 transitions. [2025-01-09 03:17:13,484 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 56 transitions. Word has length 28 [2025-01-09 03:17:13,484 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:13,484 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 56 transitions. [2025-01-09 03:17:13,484 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 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-01-09 03:17:13,484 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 56 transitions. [2025-01-09 03:17:13,485 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2025-01-09 03:17:13,485 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:13,485 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] [2025-01-09 03:17:13,491 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-01-09 03:17:13,685 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-01-09 03:17:13,686 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:13,686 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:13,686 INFO L85 PathProgramCache]: Analyzing trace with hash 747440556, now seen corresponding path program 1 times [2025-01-09 03:17:13,686 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:13,686 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524057042] [2025-01-09 03:17:13,686 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:13,686 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:13,691 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-01-09 03:17:13,710 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-01-09 03:17:13,710 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:13,710 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:13,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [446381363] [2025-01-09 03:17:13,711 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:13,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:13,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:13,712 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-01-09 03:17:13,713 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-01-09 03:17:13,735 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 33 statements into 1 equivalence classes. [2025-01-09 03:17:13,746 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 33 of 33 statements. [2025-01-09 03:17:13,746 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:13,746 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:13,747 INFO L256 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-01-09 03:17:13,748 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:13,803 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2025-01-09 03:17:13,806 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:13,807 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:13,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524057042] [2025-01-09 03:17:13,807 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:13,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [446381363] [2025-01-09 03:17:13,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [446381363] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:13,807 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:17:13,807 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:17:13,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380906753] [2025-01-09 03:17:13,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:13,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:13,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:13,808 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:13,808 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:17:13,808 INFO L87 Difference]: Start difference. First operand 39 states and 56 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-01-09 03:17:13,859 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:13,859 INFO L93 Difference]: Finished difference Result 46 states and 62 transitions. [2025-01-09 03:17:13,860 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:13,860 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 33 [2025-01-09 03:17:13,860 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:13,861 INFO L225 Difference]: With dead ends: 46 [2025-01-09 03:17:13,861 INFO L226 Difference]: Without dead ends: 44 [2025-01-09 03:17:13,861 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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-01-09 03:17:13,862 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 119 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-01-09 03:17:13,862 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 119 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:13,863 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2025-01-09 03:17:13,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 43. [2025-01-09 03:17:13,868 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 23 states have internal predecessors, (26), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2025-01-09 03:17:13,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 59 transitions. [2025-01-09 03:17:13,869 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 59 transitions. Word has length 33 [2025-01-09 03:17:13,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:13,869 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 59 transitions. [2025-01-09 03:17:13,869 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-01-09 03:17:13,869 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 59 transitions. [2025-01-09 03:17:13,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-09 03:17:13,870 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:13,870 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] [2025-01-09 03:17:13,876 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:14,070 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-01-09 03:17:14,071 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:14,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:14,071 INFO L85 PathProgramCache]: Analyzing trace with hash 965297186, now seen corresponding path program 1 times [2025-01-09 03:17:14,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:14,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1863627796] [2025-01-09 03:17:14,072 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:14,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:14,076 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-09 03:17:14,089 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 03:17:14,090 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:14,090 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:14,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1043518658] [2025-01-09 03:17:14,092 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:14,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:14,093 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:14,094 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-01-09 03:17:14,096 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-01-09 03:17:14,116 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-09 03:17:14,135 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 03:17:14,135 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:14,135 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:14,136 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-01-09 03:17:14,137 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:14,189 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 03:17:14,190 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:14,190 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:14,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1863627796] [2025-01-09 03:17:14,190 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:14,190 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1043518658] [2025-01-09 03:17:14,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1043518658] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:14,190 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:17:14,190 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:17:14,190 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [407365057] [2025-01-09 03:17:14,190 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:14,190 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:14,190 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:14,191 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:14,191 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:17:14,191 INFO L87 Difference]: Start difference. First operand 43 states and 59 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-01-09 03:17:14,237 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:14,237 INFO L93 Difference]: Finished difference Result 66 states and 97 transitions. [2025-01-09 03:17:14,237 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:14,237 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 38 [2025-01-09 03:17:14,238 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:14,239 INFO L225 Difference]: With dead ends: 66 [2025-01-09 03:17:14,239 INFO L226 Difference]: Without dead ends: 62 [2025-01-09 03:17:14,240 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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-01-09 03:17:14,240 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 118 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-01-09 03:17:14,241 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 118 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:14,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2025-01-09 03:17:14,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2025-01-09 03:17:14,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 28 states have (on average 1.3214285714285714) internal successors, (37), 32 states have internal predecessors, (37), 28 states have call successors, (28), 5 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2025-01-09 03:17:14,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 90 transitions. [2025-01-09 03:17:14,252 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 90 transitions. Word has length 38 [2025-01-09 03:17:14,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:14,252 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 90 transitions. [2025-01-09 03:17:14,252 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-01-09 03:17:14,252 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 90 transitions. [2025-01-09 03:17:14,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2025-01-09 03:17:14,253 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:14,253 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] [2025-01-09 03:17:14,259 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:14,457 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-01-09 03:17:14,457 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:14,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:14,458 INFO L85 PathProgramCache]: Analyzing trace with hash -473063785, now seen corresponding path program 1 times [2025-01-09 03:17:14,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:14,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218375425] [2025-01-09 03:17:14,458 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:14,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:14,463 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 44 statements into 1 equivalence classes. [2025-01-09 03:17:14,478 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 44 of 44 statements. [2025-01-09 03:17:14,478 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:14,478 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:14,617 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2025-01-09 03:17:14,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:14,617 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218375425] [2025-01-09 03:17:14,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1218375425] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:14,617 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:17:14,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:17:14,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [251025871] [2025-01-09 03:17:14,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:14,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:14,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:14,618 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:14,618 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:17:14,618 INFO L87 Difference]: Start difference. First operand 62 states and 90 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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-01-09 03:17:14,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:14,659 INFO L93 Difference]: Finished difference Result 68 states and 95 transitions. [2025-01-09 03:17:14,659 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:14,659 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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 44 [2025-01-09 03:17:14,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:14,660 INFO L225 Difference]: With dead ends: 68 [2025-01-09 03:17:14,660 INFO L226 Difference]: Without dead ends: 66 [2025-01-09 03:17:14,661 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-01-09 03:17:14,661 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 3 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 128 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-01-09 03:17:14,661 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 128 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:14,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-01-09 03:17:14,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2025-01-09 03:17:14,672 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 35 states have internal predecessors, (40), 28 states have call successors, (28), 6 states have call predecessors, (28), 6 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2025-01-09 03:17:14,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 93 transitions. [2025-01-09 03:17:14,676 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 93 transitions. Word has length 44 [2025-01-09 03:17:14,676 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:14,676 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 93 transitions. [2025-01-09 03:17:14,676 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 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-01-09 03:17:14,676 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 93 transitions. [2025-01-09 03:17:14,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2025-01-09 03:17:14,677 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:14,677 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:14,677 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2025-01-09 03:17:14,677 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:14,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:14,677 INFO L85 PathProgramCache]: Analyzing trace with hash -1766583019, now seen corresponding path program 1 times [2025-01-09 03:17:14,677 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:14,677 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509586622] [2025-01-09 03:17:14,677 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:14,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:14,682 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-01-09 03:17:14,690 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-01-09 03:17:14,690 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:14,690 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:14,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1817918826] [2025-01-09 03:17:14,691 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:14,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:14,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:14,693 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-01-09 03:17:14,695 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-01-09 03:17:14,716 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 45 statements into 1 equivalence classes. [2025-01-09 03:17:14,731 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 45 of 45 statements. [2025-01-09 03:17:14,731 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:14,731 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:14,732 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-01-09 03:17:14,733 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:14,794 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2025-01-09 03:17:14,794 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:14,794 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:14,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509586622] [2025-01-09 03:17:14,794 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:14,794 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1817918826] [2025-01-09 03:17:14,794 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1817918826] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:14,794 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:17:14,794 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:17:14,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [365359354] [2025-01-09 03:17:14,794 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:14,795 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:14,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:14,795 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:14,795 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:17:14,795 INFO L87 Difference]: Start difference. First operand 66 states and 93 transitions. Second operand has 5 states, 5 states have (on average 3.0) 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), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 03:17:14,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:14,838 INFO L93 Difference]: Finished difference Result 76 states and 101 transitions. [2025-01-09 03:17:14,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:14,839 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) 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), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2025-01-09 03:17:14,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:14,840 INFO L225 Difference]: With dead ends: 76 [2025-01-09 03:17:14,840 INFO L226 Difference]: Without dead ends: 73 [2025-01-09 03:17:14,840 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 41 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-01-09 03:17:14,840 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:17:14,840 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 120 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:14,841 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-01-09 03:17:14,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2025-01-09 03:17:14,852 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 37 states have (on average 1.2432432432432432) internal successors, (46), 40 states have internal predecessors, (46), 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-01-09 03:17:14,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2025-01-09 03:17:14,852 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 45 [2025-01-09 03:17:14,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:14,853 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2025-01-09 03:17:14,853 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) 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), 2 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-09 03:17:14,853 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2025-01-09 03:17:14,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-01-09 03:17:14,854 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:14,854 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] [2025-01-09 03:17:14,860 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:15,054 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-01-09 03:17:15,055 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:15,055 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:15,055 INFO L85 PathProgramCache]: Analyzing trace with hash 683817367, now seen corresponding path program 1 times [2025-01-09 03:17:15,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:15,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [879264771] [2025-01-09 03:17:15,055 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:15,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:15,061 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 03:17:15,071 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 03:17:15,072 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:15,073 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:15,259 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-01-09 03:17:15,259 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:15,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [879264771] [2025-01-09 03:17:15,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [879264771] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 03:17:15,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1104310539] [2025-01-09 03:17:15,259 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:15,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:15,260 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:15,261 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-01-09 03:17:15,263 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-01-09 03:17:15,281 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 49 statements into 1 equivalence classes. [2025-01-09 03:17:15,293 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 49 of 49 statements. [2025-01-09 03:17:15,293 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:15,293 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:15,294 INFO L256 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-01-09 03:17:15,295 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:15,363 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-01-09 03:17:15,364 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:17:15,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1104310539] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:17:15,364 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 03:17:15,364 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2025-01-09 03:17:15,364 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700607121] [2025-01-09 03:17:15,364 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:15,364 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-09 03:17:15,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:15,365 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-09 03:17:15,365 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2025-01-09 03:17:15,365 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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-01-09 03:17:15,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:15,431 INFO L93 Difference]: Finished difference Result 84 states and 106 transitions. [2025-01-09 03:17:15,431 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-01-09 03:17:15,431 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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 49 [2025-01-09 03:17:15,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:15,432 INFO L225 Difference]: With dead ends: 84 [2025-01-09 03:17:15,432 INFO L226 Difference]: Without dead ends: 80 [2025-01-09 03:17:15,433 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 48 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-01-09 03:17:15,433 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 142 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.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:17:15,433 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 142 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:15,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2025-01-09 03:17:15,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 79. [2025-01-09 03:17:15,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 43 states have (on average 1.186046511627907) internal successors, (51), 46 states have internal predecessors, (51), 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-01-09 03:17:15,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 99 transitions. [2025-01-09 03:17:15,441 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 99 transitions. Word has length 49 [2025-01-09 03:17:15,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:15,441 INFO L471 AbstractCegarLoop]: Abstraction has 79 states and 99 transitions. [2025-01-09 03:17:15,441 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 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-01-09 03:17:15,442 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 99 transitions. [2025-01-09 03:17:15,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-01-09 03:17:15,442 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:15,442 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:15,448 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:15,647 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-01-09 03:17:15,647 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:15,647 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:15,647 INFO L85 PathProgramCache]: Analyzing trace with hash -2011112807, now seen corresponding path program 2 times [2025-01-09 03:17:15,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:15,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [381430042] [2025-01-09 03:17:15,647 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 03:17:15,648 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:15,652 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-01-09 03:17:15,666 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-01-09 03:17:15,666 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 03:17:15,666 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:15,666 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [659110852] [2025-01-09 03:17:15,666 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 03:17:15,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:15,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:15,670 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-01-09 03:17:15,671 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-01-09 03:17:15,692 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-01-09 03:17:15,707 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-01-09 03:17:15,707 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 03:17:15,707 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:15,708 INFO L256 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 27 conjuncts are in the unsatisfiable core [2025-01-09 03:17:15,709 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:15,868 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 17 proven. 2 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2025-01-09 03:17:15,868 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:17:16,031 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2025-01-09 03:17:16,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:16,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [381430042] [2025-01-09 03:17:16,032 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:16,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [659110852] [2025-01-09 03:17:16,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [659110852] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 03:17:16,032 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 03:17:16,032 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 11 [2025-01-09 03:17:16,032 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [155236911] [2025-01-09 03:17:16,032 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 03:17:16,033 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 03:17:16,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:16,033 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 03:17:16,033 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2025-01-09 03:17:16,033 INFO L87 Difference]: Start difference. First operand 79 states and 99 transitions. Second operand has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2025-01-09 03:17:16,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:16,426 INFO L93 Difference]: Finished difference Result 124 states and 174 transitions. [2025-01-09 03:17:16,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2025-01-09 03:17:16,427 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) Word has length 50 [2025-01-09 03:17:16,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:16,428 INFO L225 Difference]: With dead ends: 124 [2025-01-09 03:17:16,428 INFO L226 Difference]: Without dead ends: 122 [2025-01-09 03:17:16,429 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 87 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2025-01-09 03:17:16,429 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 39 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 179 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 222 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 179 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 03:17:16,429 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 198 Invalid, 222 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 179 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 03:17:16,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2025-01-09 03:17:16,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 102. [2025-01-09 03:17:16,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 55 states have (on average 1.2545454545454546) internal successors, (69), 58 states have internal predecessors, (69), 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-01-09 03:17:16,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 135 transitions. [2025-01-09 03:17:16,451 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 135 transitions. Word has length 50 [2025-01-09 03:17:16,451 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:16,451 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 135 transitions. [2025-01-09 03:17:16,451 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 6 states have call predecessors, (13), 5 states have call successors, (13) [2025-01-09 03:17:16,451 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 135 transitions. [2025-01-09 03:17:16,452 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2025-01-09 03:17:16,452 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:16,452 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:16,457 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:16,652 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-01-09 03:17:16,653 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:16,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:16,654 INFO L85 PathProgramCache]: Analyzing trace with hash 1509610455, now seen corresponding path program 1 times [2025-01-09 03:17:16,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:16,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764191653] [2025-01-09 03:17:16,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:16,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:16,660 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-01-09 03:17:16,671 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-01-09 03:17:16,673 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:16,673 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:16,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1112289968] [2025-01-09 03:17:16,675 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:16,675 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:16,675 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:16,677 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-01-09 03:17:16,678 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-01-09 03:17:16,700 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 55 statements into 1 equivalence classes. [2025-01-09 03:17:16,715 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 55 of 55 statements. [2025-01-09 03:17:16,715 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:16,715 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:16,716 INFO L256 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 31 conjuncts are in the unsatisfiable core [2025-01-09 03:17:16,717 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:16,921 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 22 proven. 3 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2025-01-09 03:17:16,921 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:17:17,013 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2025-01-09 03:17:17,013 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:17,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1764191653] [2025-01-09 03:17:17,013 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:17,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1112289968] [2025-01-09 03:17:17,013 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1112289968] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 03:17:17,013 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 03:17:17,013 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2025-01-09 03:17:17,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1796959491] [2025-01-09 03:17:17,014 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 03:17:17,015 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-01-09 03:17:17,015 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:17,015 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-01-09 03:17:17,015 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2025-01-09 03:17:17,015 INFO L87 Difference]: Start difference. First operand 102 states and 135 transitions. Second operand has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2025-01-09 03:17:17,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:17,382 INFO L93 Difference]: Finished difference Result 115 states and 153 transitions. [2025-01-09 03:17:17,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-09 03:17:17,382 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) Word has length 55 [2025-01-09 03:17:17,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:17,383 INFO L225 Difference]: With dead ends: 115 [2025-01-09 03:17:17,383 INFO L226 Difference]: Without dead ends: 97 [2025-01-09 03:17:17,383 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 96 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2025-01-09 03:17:17,384 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 16 mSDsluCounter, 226 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 03:17:17,384 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 255 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 03:17:17,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2025-01-09 03:17:17,397 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 94. [2025-01-09 03:17:17,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 52 states have (on average 1.2307692307692308) internal successors, (64), 54 states have internal predecessors, (64), 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-01-09 03:17:17,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 122 transitions. [2025-01-09 03:17:17,398 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 122 transitions. Word has length 55 [2025-01-09 03:17:17,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:17,398 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 122 transitions. [2025-01-09 03:17:17,398 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 9 states have internal predecessors, (21), 6 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2025-01-09 03:17:17,398 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 122 transitions. [2025-01-09 03:17:17,399 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2025-01-09 03:17:17,399 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:17,399 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:17,404 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-01-09 03:17:17,603 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-01-09 03:17:17,603 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:17,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:17,603 INFO L85 PathProgramCache]: Analyzing trace with hash 1920539012, now seen corresponding path program 1 times [2025-01-09 03:17:17,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:17,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [695379407] [2025-01-09 03:17:17,603 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:17,603 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:17,607 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-01-09 03:17:17,621 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-01-09 03:17:17,622 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:17,622 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:17:17,622 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [719700985] [2025-01-09 03:17:17,622 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:17,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:17,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:17,626 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-01-09 03:17:17,627 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-01-09 03:17:17,647 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 62 statements into 1 equivalence classes. [2025-01-09 03:17:17,662 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 62 of 62 statements. [2025-01-09 03:17:17,662 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:17,662 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:17,663 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 19 conjuncts are in the unsatisfiable core [2025-01-09 03:17:17,667 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:17,770 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2025-01-09 03:17:17,770 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:17:17,861 INFO L134 CoverageAnalysis]: Checked inductivity of 103 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2025-01-09 03:17:17,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:17,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [695379407] [2025-01-09 03:17:17,862 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:17:17,862 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [719700985] [2025-01-09 03:17:17,862 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [719700985] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 03:17:17,862 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 03:17:17,862 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2025-01-09 03:17:17,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460764755] [2025-01-09 03:17:17,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:17:17,862 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:17:17,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:17,863 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:17:17,863 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2025-01-09 03:17:17,863 INFO L87 Difference]: Start difference. First operand 94 states and 122 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-01-09 03:17:17,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:17,913 INFO L93 Difference]: Finished difference Result 100 states and 127 transitions. [2025-01-09 03:17:17,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:17:17,913 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 62 [2025-01-09 03:17:17,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:17,916 INFO L225 Difference]: With dead ends: 100 [2025-01-09 03:17:17,917 INFO L226 Difference]: Without dead ends: 95 [2025-01-09 03:17:17,917 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 114 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-01-09 03:17:17,917 INFO L435 NwaCegarLoop]: 30 mSDtfsCounter, 4 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 106 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-01-09 03:17:17,918 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 106 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:17:17,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2025-01-09 03:17:17,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 93. [2025-01-09 03:17:17,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 54 states have (on average 1.2037037037037037) internal successors, (65), 54 states have internal predecessors, (65), 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-01-09 03:17:17,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 118 transitions. [2025-01-09 03:17:17,937 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 118 transitions. Word has length 62 [2025-01-09 03:17:17,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:17,937 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 118 transitions. [2025-01-09 03:17:17,937 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-01-09 03:17:17,937 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 118 transitions. [2025-01-09 03:17:17,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2025-01-09 03:17:17,938 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:17:17,938 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1, 1] [2025-01-09 03:17:17,945 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2025-01-09 03:17:18,144 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-01-09 03:17:18,144 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:17:18,144 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:17:18,144 INFO L85 PathProgramCache]: Analyzing trace with hash -1342664572, now seen corresponding path program 1 times [2025-01-09 03:17:18,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:17:18,144 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1701317210] [2025-01-09 03:17:18,144 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:18,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:17:18,151 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-01-09 03:17:18,160 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-01-09 03:17:18,160 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:18,160 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:18,280 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-01-09 03:17:18,280 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:17:18,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1701317210] [2025-01-09 03:17:18,280 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1701317210] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 03:17:18,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1095708850] [2025-01-09 03:17:18,280 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:17:18,280 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:17:18,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:17:18,282 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-01-09 03:17:18,283 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-01-09 03:17:18,303 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 66 statements into 1 equivalence classes. [2025-01-09 03:17:18,315 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 66 of 66 statements. [2025-01-09 03:17:18,315 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:17:18,315 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:17:18,316 INFO L256 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-01-09 03:17:18,318 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:17:18,355 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-01-09 03:17:18,356 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:17:18,431 INFO L134 CoverageAnalysis]: Checked inductivity of 126 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2025-01-09 03:17:18,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1095708850] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 03:17:18,431 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 03:17:18,431 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2025-01-09 03:17:18,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1919779673] [2025-01-09 03:17:18,432 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 03:17:18,432 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2025-01-09 03:17:18,432 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:17:18,432 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2025-01-09 03:17:18,432 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2025-01-09 03:17:18,432 INFO L87 Difference]: Start difference. First operand 93 states and 118 transitions. Second operand has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 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-01-09 03:17:18,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:17:18,507 INFO L93 Difference]: Finished difference Result 103 states and 128 transitions. [2025-01-09 03:17:18,508 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2025-01-09 03:17:18,508 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 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 66 [2025-01-09 03:17:18,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:17:18,508 INFO L225 Difference]: With dead ends: 103 [2025-01-09 03:17:18,508 INFO L226 Difference]: Without dead ends: 0 [2025-01-09 03:17:18,509 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 128 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-01-09 03:17:18,509 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 9 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 03:17:18,509 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 120 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 03:17:18,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-01-09 03:17:18,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-01-09 03:17:18,509 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-01-09 03:17:18,509 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-01-09 03:17:18,510 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 66 [2025-01-09 03:17:18,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:17:18,510 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-01-09 03:17:18,510 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 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-01-09 03:17:18,510 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-01-09 03:17:18,510 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-01-09 03:17:18,512 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-01-09 03:17:18,517 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2025-01-09 03:17:18,712 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-01-09 03:17:18,715 INFO L422 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:17:18,716 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-01-09 03:17:26,547 WARN L286 SmtUtils]: Spent 6.71s on a formula simplification. DAG size of input: 70 DAG size of output: 35 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2025-01-09 03:17:48,718 WARN L286 SmtUtils]: Spent 18.15s on a formula simplification. DAG size of input: 57 DAG size of output: 36 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2025-01-09 03:17:53,237 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-01-09 03:17:53,246 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.01 03:17:53 BoogieIcfgContainer [2025-01-09 03:17:53,247 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-01-09 03:17:53,247 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-01-09 03:17:53,247 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-01-09 03:17:53,247 INFO L274 PluginConnector]: Witness Printer initialized [2025-01-09 03:17:53,248 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:17:12" (3/4) ... [2025-01-09 03:17:53,249 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-01-09 03:17:53,253 INFO L362 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2025-01-09 03:17:53,254 INFO L362 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-01-09 03:17:53,256 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2025-01-09 03:17:53,256 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-01-09 03:17:53,256 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-01-09 03:17:53,256 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-01-09 03:17:53,306 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-01-09 03:17:53,307 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.yml [2025-01-09 03:17:53,307 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-01-09 03:17:53,307 INFO L158 Benchmark]: Toolchain (without parser) took 41076.95ms. Allocated memory is still 167.8MB. Free memory was 123.0MB in the beginning and 71.0MB in the end (delta: 52.0MB). Peak memory consumption was 50.0MB. Max. memory is 16.1GB. [2025-01-09 03:17:53,307 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 201.3MB. Free memory is still 115.8MB. There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: CACSL2BoogieTranslator took 178.96ms. Allocated memory is still 167.8MB. Free memory was 123.0MB in the beginning and 111.5MB in the end (delta: 11.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.44ms. Allocated memory is still 167.8MB. Free memory was 111.5MB in the beginning and 110.5MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: Boogie Preprocessor took 30.12ms. Allocated memory is still 167.8MB. Free memory was 110.5MB in the beginning and 109.0MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: RCFGBuilder took 230.93ms. Allocated memory is still 167.8MB. Free memory was 109.0MB in the beginning and 96.9MB in the end (delta: 12.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: TraceAbstraction took 40547.40ms. Allocated memory is still 167.8MB. Free memory was 96.9MB in the beginning and 76.2MB in the end (delta: 20.7MB). Peak memory consumption was 59.4MB. Max. memory is 16.1GB. [2025-01-09 03:17:53,308 INFO L158 Benchmark]: Witness Printer took 59.65ms. Allocated memory is still 167.8MB. Free memory was 76.2MB in the beginning and 71.0MB in the end (delta: 5.2MB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 03:17:53,309 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.19ms. Allocated memory is still 201.3MB. Free memory is still 115.8MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 178.96ms. Allocated memory is still 167.8MB. Free memory was 123.0MB in the beginning and 111.5MB in the end (delta: 11.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.44ms. Allocated memory is still 167.8MB. Free memory was 111.5MB in the beginning and 110.5MB in the end (delta: 1.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 30.12ms. Allocated memory is still 167.8MB. Free memory was 110.5MB in the beginning and 109.0MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 230.93ms. Allocated memory is still 167.8MB. Free memory was 109.0MB in the beginning and 96.9MB in the end (delta: 12.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 40547.40ms. Allocated memory is still 167.8MB. Free memory was 96.9MB in the beginning and 76.2MB in the end (delta: 20.7MB). Peak memory consumption was 59.4MB. Max. memory is 16.1GB. * Witness Printer took 59.65ms. Allocated memory is still 167.8MB. Free memory was 76.2MB in the beginning and 71.0MB in the end (delta: 5.2MB). There was no memory consumed. 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, 31 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 6.0s, OverallIterations: 11, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 126 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 98 mSDsluCounter, 1464 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1113 mSDsCounter, 91 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 682 IncrementalHoareTripleChecker+Invalid, 773 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 91 mSolverCounterUnsat, 351 mSDtfsCounter, 682 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 717 GetRequests, 633 SyntacticMatches, 8 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=102occurred in iteration=8, InterpolantAutomatonStates: 70, 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, 30 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.8s InterpolantComputationTime, 952 NumberOfCodeBlocks, 952 NumberOfCodeBlocksAsserted, 23 NumberOfCheckSat, 856 ConstructedInterpolants, 0 QuantifiedInterpolants, 2217 SizeOfPredicates, 18 NumberOfNonLiveVariables, 1160 ConjunctsInSsa, 140 ConjunctsInUnsatCore, 18 InterpolantComputations, 8 PerfectInterpolantSequences, 1130/1181 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]: Loop Invariant Derived loop 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)))) && (1 <= x)) RESULT: Ultimate proved your program to be correct! [2025-01-09 03:17:53,325 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