./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c00e63dc Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i -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 a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 --- Real Ultimate output --- This is Ultimate 0.3.0-?-c00e63d-m [2025-02-05 17:29:57,515 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-05 17:29:57,563 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-02-05 17:29:57,569 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-05 17:29:57,570 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-05 17:29:57,592 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-05 17:29:57,592 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-05 17:29:57,593 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-05 17:29:57,593 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-05 17:29:57,593 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-05 17:29:57,594 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-05 17:29:57,594 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-05 17:29:57,594 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-05 17:29:57,594 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-05 17:29:57,594 INFO L153 SettingsManager]: * Use SBE=true [2025-02-05 17:29:57,595 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-05 17:29:57,595 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-05 17:29:57,595 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-05 17:29:57,595 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-05 17:29:57,596 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-05 17:29:57,596 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 17:29:57,597 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-05 17:29:57,597 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-05 17:29:57,597 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 -> a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 [2025-02-05 17:29:57,796 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-05 17:29:57,803 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-05 17:29:57,804 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-05 17:29:57,805 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-05 17:29:57,805 INFO L274 PluginConnector]: CDTParser initialized [2025-02-05 17:29:57,805 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-02-05 17:29:58,917 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a5d00e80f/de459efa1b744069a5a8bee60d93d1c6/FLAGc913af119 [2025-02-05 17:29:59,137 INFO L384 CDTParser]: Found 1 translation units. [2025-02-05 17:29:59,142 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-02-05 17:29:59,150 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a5d00e80f/de459efa1b744069a5a8bee60d93d1c6/FLAGc913af119 [2025-02-05 17:29:59,488 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/a5d00e80f/de459efa1b744069a5a8bee60d93d1c6 [2025-02-05 17:29:59,490 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-05 17:29:59,492 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-05 17:29:59,494 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-05 17:29:59,494 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-05 17:29:59,497 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-05 17:29:59,498 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,500 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@dbd03ba and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59, skipping insertion in model container [2025-02-05 17:29:59,500 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,513 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-05 17:29:59,625 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/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-02-05 17:29:59,645 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/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-02-05 17:29:59,646 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 17:29:59,655 INFO L200 MainTranslator]: Completed pre-run [2025-02-05 17:29:59,669 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/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-02-05 17:29:59,678 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/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-02-05 17:29:59,682 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 17:29:59,697 INFO L204 MainTranslator]: Completed translation [2025-02-05 17:29:59,698 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59 WrapperNode [2025-02-05 17:29:59,698 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-05 17:29:59,699 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-05 17:29:59,702 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-05 17:29:59,702 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-05 17:29:59,706 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,714 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,726 INFO L138 Inliner]: procedures = 27, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 76 [2025-02-05 17:29:59,726 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-05 17:29:59,727 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-05 17:29:59,727 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-05 17:29:59,727 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-05 17:29:59,731 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,731 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,732 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,746 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-02-05 17:29:59,746 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,746 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,749 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,749 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,750 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,750 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,751 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-05 17:29:59,752 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-05 17:29:59,752 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-05 17:29:59,752 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-05 17:29:59,756 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (1/1) ... [2025-02-05 17:29:59,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 17:29:59,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:29:59,775 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-05 17:29:59,777 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-05 17:29:59,790 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-05 17:29:59,790 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-02-05 17:29:59,791 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-02-05 17:29:59,791 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-02-05 17:29:59,791 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-02-05 17:29:59,791 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-02-05 17:29:59,791 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-02-05 17:29:59,791 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-05 17:29:59,791 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-05 17:29:59,791 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-02-05 17:29:59,791 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-02-05 17:29:59,830 INFO L257 CfgBuilder]: Building ICFG [2025-02-05 17:29:59,831 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-05 17:29:59,957 INFO L? ?]: Removed 23 outVars from TransFormulas that were not future-live. [2025-02-05 17:29:59,957 INFO L308 CfgBuilder]: Performing block encoding [2025-02-05 17:29:59,962 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-05 17:29:59,963 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-05 17:29:59,963 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 05:29:59 BoogieIcfgContainer [2025-02-05 17:29:59,963 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-05 17:29:59,964 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-05 17:29:59,964 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-05 17:29:59,967 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-05 17:29:59,967 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.02 05:29:59" (1/3) ... [2025-02-05 17:29:59,968 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d8e4c53 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 05:29:59, skipping insertion in model container [2025-02-05 17:29:59,968 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:29:59" (2/3) ... [2025-02-05 17:29:59,968 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d8e4c53 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 05:29:59, skipping insertion in model container [2025-02-05 17:29:59,968 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 05:29:59" (3/3) ... [2025-02-05 17:29:59,969 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_3.i [2025-02-05 17:29:59,977 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-05 17:29:59,978 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_3.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-02-05 17:30:00,005 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-05 17:30:00,013 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;@732556c8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-05 17:30:00,013 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-02-05 17:30:00,015 INFO L276 IsEmpty]: Start isEmpty. Operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-02-05 17:30:00,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-02-05 17:30:00,019 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:00,019 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:00,019 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:00,022 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:00,023 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-02-05 17:30:00,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:00,028 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [84510403] [2025-02-05 17:30:00,028 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:00,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:00,068 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-02-05 17:30:00,080 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-02-05 17:30:00,081 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:00,081 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:00,158 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:00,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [84510403] [2025-02-05 17:30:00,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [84510403] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 17:30:00,159 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 17:30:00,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-05 17:30:00,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1486925096] [2025-02-05 17:30:00,160 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 17:30:00,162 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-05 17:30:00,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:00,172 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-05 17:30:00,173 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,174 INFO L87 Difference]: Start difference. First operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:00,199 INFO L93 Difference]: Finished difference Result 80 states and 105 transitions. [2025-02-05 17:30:00,199 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-05 17:30:00,200 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-02-05 17:30:00,200 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:00,203 INFO L225 Difference]: With dead ends: 80 [2025-02-05 17:30:00,203 INFO L226 Difference]: Without dead ends: 37 [2025-02-05 17:30:00,205 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,206 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 5 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:00,207 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 84 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 17:30:00,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-02-05 17:30:00,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-02-05 17:30:00,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.28) internal successors, (32), 27 states have internal predecessors, (32), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:00,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 45 transitions. [2025-02-05 17:30:00,227 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 45 transitions. Word has length 11 [2025-02-05 17:30:00,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:00,227 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 45 transitions. [2025-02-05 17:30:00,227 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,227 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 45 transitions. [2025-02-05 17:30:00,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-02-05 17:30:00,228 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:00,228 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:00,228 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-02-05 17:30:00,228 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:00,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:00,229 INFO L85 PathProgramCache]: Analyzing trace with hash -264142809, now seen corresponding path program 1 times [2025-02-05 17:30:00,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:00,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657622178] [2025-02-05 17:30:00,229 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:00,229 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:00,235 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-02-05 17:30:00,238 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-02-05 17:30:00,238 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:00,238 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:00,281 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,281 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:00,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657622178] [2025-02-05 17:30:00,282 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [657622178] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 17:30:00,282 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 17:30:00,282 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-05 17:30:00,282 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1251141985] [2025-02-05 17:30:00,282 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 17:30:00,283 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-05 17:30:00,283 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:00,283 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-05 17:30:00,283 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,284 INFO L87 Difference]: Start difference. First operand 37 states and 45 transitions. Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:00,297 INFO L93 Difference]: Finished difference Result 57 states and 73 transitions. [2025-02-05 17:30:00,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-05 17:30:00,298 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-02-05 17:30:00,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:00,298 INFO L225 Difference]: With dead ends: 57 [2025-02-05 17:30:00,299 INFO L226 Difference]: Without dead ends: 41 [2025-02-05 17:30:00,299 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,299 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:00,300 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 67 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 17:30:00,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2025-02-05 17:30:00,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 37. [2025-02-05 17:30:00,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:00,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-02-05 17:30:00,304 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 11 [2025-02-05 17:30:00,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:00,304 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-02-05 17:30:00,304 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,304 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-02-05 17:30:00,304 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-02-05 17:30:00,304 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:00,305 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:00,305 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-02-05 17:30:00,305 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:00,305 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:00,305 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-02-05 17:30:00,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:00,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [639174329] [2025-02-05 17:30:00,305 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:00,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:00,313 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-02-05 17:30:00,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-02-05 17:30:00,319 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:00,319 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:00,383 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,383 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:00,383 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [639174329] [2025-02-05 17:30:00,383 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [639174329] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 17:30:00,383 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 17:30:00,383 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-05 17:30:00,383 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2460967] [2025-02-05 17:30:00,383 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 17:30:00,384 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-05 17:30:00,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:00,384 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-05 17:30:00,384 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,385 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,406 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:00,406 INFO L93 Difference]: Finished difference Result 51 states and 61 transitions. [2025-02-05 17:30:00,406 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-05 17:30:00,407 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2025-02-05 17:30:00,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:00,407 INFO L225 Difference]: With dead ends: 51 [2025-02-05 17:30:00,407 INFO L226 Difference]: Without dead ends: 39 [2025-02-05 17:30:00,408 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:00,408 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:00,408 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 66 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 17:30:00,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2025-02-05 17:30:00,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2025-02-05 17:30:00,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:00,421 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2025-02-05 17:30:00,421 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 14 [2025-02-05 17:30:00,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:00,421 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2025-02-05 17:30:00,421 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,421 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2025-02-05 17:30:00,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-02-05 17:30:00,422 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:00,422 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:00,422 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-02-05 17:30:00,422 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:00,422 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:00,422 INFO L85 PathProgramCache]: Analyzing trace with hash -1424638767, now seen corresponding path program 1 times [2025-02-05 17:30:00,422 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:00,422 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107154543] [2025-02-05 17:30:00,422 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:00,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:00,431 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-02-05 17:30:00,437 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-02-05 17:30:00,437 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:00,437 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:00,530 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:00,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2107154543] [2025-02-05 17:30:00,530 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2107154543] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 17:30:00,530 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [90965274] [2025-02-05 17:30:00,530 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:00,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:00,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:00,532 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:00,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-05 17:30:00,567 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-02-05 17:30:00,578 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-02-05 17:30:00,578 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:00,578 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:00,579 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-02-05 17:30:00,581 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:00,637 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,637 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:00,688 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:00,689 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [90965274] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:00,689 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-05 17:30:00,689 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5, 5] total 10 [2025-02-05 17:30:00,689 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1410023822] [2025-02-05 17:30:00,689 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:00,692 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-02-05 17:30:00,693 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:00,693 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-02-05 17:30:00,693 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-02-05 17:30:00,693 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:00,725 INFO L93 Difference]: Finished difference Result 55 states and 66 transitions. [2025-02-05 17:30:00,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 17:30:00,725 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 16 [2025-02-05 17:30:00,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:00,725 INFO L225 Difference]: With dead ends: 55 [2025-02-05 17:30:00,725 INFO L226 Difference]: Without dead ends: 43 [2025-02-05 17:30:00,726 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-02-05 17:30:00,726 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 159 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:00,726 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 159 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-02-05 17:30:00,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2025-02-05 17:30:00,729 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2025-02-05 17:30:00,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:00,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2025-02-05 17:30:00,730 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 16 [2025-02-05 17:30:00,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:00,730 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2025-02-05 17:30:00,730 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:00,730 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2025-02-05 17:30:00,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-02-05 17:30:00,731 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:00,731 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:00,737 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-02-05 17:30:00,934 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:00,935 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:00,935 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:00,935 INFO L85 PathProgramCache]: Analyzing trace with hash 793720653, now seen corresponding path program 2 times [2025-02-05 17:30:00,935 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:00,936 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [705396723] [2025-02-05 17:30:00,936 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 17:30:00,936 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:00,940 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-02-05 17:30:00,948 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-02-05 17:30:00,948 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 17:30:00,948 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:01,045 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:01,045 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:01,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [705396723] [2025-02-05 17:30:01,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [705396723] provided 0 perfect and 1 imperfect interpolant sequences [2025-02-05 17:30:01,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [202224211] [2025-02-05 17:30:01,046 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 17:30:01,046 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:01,046 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:01,047 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:01,049 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-05 17:30:01,073 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-02-05 17:30:01,083 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-02-05 17:30:01,083 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 17:30:01,083 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:01,084 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-02-05 17:30:01,085 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:01,206 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:01,206 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:01,318 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:01,318 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [202224211] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:01,318 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-02-05 17:30:01,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2025-02-05 17:30:01,319 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1028026895] [2025-02-05 17:30:01,319 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:01,319 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-02-05 17:30:01,319 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:01,319 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-02-05 17:30:01,320 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=175, Unknown=0, NotChecked=0, Total=272 [2025-02-05 17:30:01,320 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:01,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:01,403 INFO L93 Difference]: Finished difference Result 64 states and 81 transitions. [2025-02-05 17:30:01,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-02-05 17:30:01,403 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 20 [2025-02-05 17:30:01,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:01,404 INFO L225 Difference]: With dead ends: 64 [2025-02-05 17:30:01,404 INFO L226 Difference]: Without dead ends: 50 [2025-02-05 17:30:01,404 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=121, Invalid=221, Unknown=0, NotChecked=0, Total=342 [2025-02-05 17:30:01,405 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:01,405 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 282 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-05 17:30:01,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2025-02-05 17:30:01,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 48. [2025-02-05 17:30:01,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 38 states have internal predecessors, (41), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:01,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2025-02-05 17:30:01,409 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 20 [2025-02-05 17:30:01,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:01,409 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2025-02-05 17:30:01,409 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 17 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:01,409 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2025-02-05 17:30:01,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-02-05 17:30:01,409 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:01,409 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:01,424 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-02-05 17:30:01,610 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:01,610 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:01,610 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:01,610 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 3 times [2025-02-05 17:30:01,610 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:01,611 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [351283027] [2025-02-05 17:30:01,611 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-05 17:30:01,611 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:01,615 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-02-05 17:30:01,631 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 22 of 22 statements. [2025-02-05 17:30:01,631 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-02-05 17:30:01,631 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-02-05 17:30:01,634 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1386506260] [2025-02-05 17:30:01,634 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-02-05 17:30:01,634 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:01,634 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:01,636 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:01,637 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-05 17:30:01,662 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-02-05 17:30:01,673 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 18 of 22 statements. [2025-02-05 17:30:01,673 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-02-05 17:30:01,673 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:01,674 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-02-05 17:30:01,675 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:01,764 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-02-05 17:30:01,765 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:01,974 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-02-05 17:30:01,975 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-02-05 17:30:01,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [351283027] [2025-02-05 17:30:01,975 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-02-05 17:30:01,975 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1386506260] [2025-02-05 17:30:01,975 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1386506260] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:01,975 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 17:30:01,975 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2025-02-05 17:30:01,976 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2055484421] [2025-02-05 17:30:01,976 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:01,976 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-02-05 17:30:01,976 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-02-05 17:30:01,976 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-02-05 17:30:01,977 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2025-02-05 17:30:01,977 INFO L87 Difference]: Start difference. First operand 48 states and 54 transitions. Second operand has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:02,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:02,266 INFO L93 Difference]: Finished difference Result 69 states and 83 transitions. [2025-02-05 17:30:02,266 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-02-05 17:30:02,266 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 22 [2025-02-05 17:30:02,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:02,267 INFO L225 Difference]: With dead ends: 69 [2025-02-05 17:30:02,267 INFO L226 Difference]: Without dead ends: 66 [2025-02-05 17:30:02,267 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=60, Invalid=320, Unknown=0, NotChecked=0, Total=380 [2025-02-05 17:30:02,268 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 8 mSDsluCounter, 350 mSDsCounter, 0 mSdLazyCounter, 236 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 381 SdHoareTripleChecker+Invalid, 246 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 236 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:02,268 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 381 Invalid, 246 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 236 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-05 17:30:02,268 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2025-02-05 17:30:02,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 63. [2025-02-05 17:30:02,273 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 47 states have (on average 1.2127659574468086) internal successors, (57), 51 states have internal predecessors, (57), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-02-05 17:30:02,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2025-02-05 17:30:02,274 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 22 [2025-02-05 17:30:02,274 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:02,274 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2025-02-05 17:30:02,274 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.0714285714285716) internal successors, (29), 14 states have internal predecessors, (29), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:02,275 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2025-02-05 17:30:02,275 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-02-05 17:30:02,275 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:02,275 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:02,281 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-05 17:30:02,476 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:02,476 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:02,476 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:02,476 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-02-05 17:30:02,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-02-05 17:30:02,477 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172581129] [2025-02-05 17:30:02,477 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:02,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-02-05 17:30:02,481 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-02-05 17:30:02,483 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-02-05 17:30:02,484 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:02,484 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-05 17:30:02,484 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-02-05 17:30:02,485 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-02-05 17:30:02,486 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-02-05 17:30:02,486 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:02,487 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-02-05 17:30:02,495 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-02-05 17:30:02,495 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-02-05 17:30:02,496 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2025-02-05 17:30:02,497 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2025-02-05 17:30:02,497 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2025-02-05 17:30:02,502 INFO L422 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1] [2025-02-05 17:30:02,514 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-02-05 17:30:02,516 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.02 05:30:02 BoogieIcfgContainer [2025-02-05 17:30:02,516 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-02-05 17:30:02,516 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-02-05 17:30:02,517 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-02-05 17:30:02,517 INFO L274 PluginConnector]: Witness Printer initialized [2025-02-05 17:30:02,517 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 05:29:59" (3/4) ... [2025-02-05 17:30:02,518 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-02-05 17:30:02,519 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-02-05 17:30:02,519 INFO L158 Benchmark]: Toolchain (without parser) took 3027.08ms. Allocated memory is still 142.6MB. Free memory was 111.5MB in the beginning and 83.9MB in the end (delta: 27.6MB). Peak memory consumption was 26.6MB. Max. memory is 16.1GB. [2025-02-05 17:30:02,519 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 201.3MB. Free memory is still 126.9MB. There was no memory consumed. Max. memory is 16.1GB. [2025-02-05 17:30:02,520 INFO L158 Benchmark]: CACSL2BoogieTranslator took 204.29ms. Allocated memory is still 142.6MB. Free memory was 111.5MB in the beginning and 99.2MB in the end (delta: 12.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 17:30:02,520 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.56ms. Allocated memory is still 142.6MB. Free memory was 99.2MB in the beginning and 98.4MB in the end (delta: 827.5kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-05 17:30:02,520 INFO L158 Benchmark]: Boogie Preprocessor took 24.69ms. Allocated memory is still 142.6MB. Free memory was 98.4MB in the beginning and 96.6MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 17:30:02,520 INFO L158 Benchmark]: IcfgBuilder took 211.29ms. Allocated memory is still 142.6MB. Free memory was 96.6MB in the beginning and 82.4MB in the end (delta: 14.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-02-05 17:30:02,520 INFO L158 Benchmark]: TraceAbstraction took 2551.91ms. Allocated memory is still 142.6MB. Free memory was 81.6MB in the beginning and 83.9MB in the end (delta: -2.3MB). Peak memory consumption was 1.4MB. Max. memory is 16.1GB. [2025-02-05 17:30:02,521 INFO L158 Benchmark]: Witness Printer took 2.47ms. Allocated memory is still 142.6MB. Free memory was 83.9MB in the beginning and 83.9MB in the end (delta: 37.0kB). There was no memory consumed. Max. memory is 16.1GB. [2025-02-05 17:30:02,522 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.16ms. Allocated memory is still 201.3MB. Free memory is still 126.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 204.29ms. Allocated memory is still 142.6MB. Free memory was 111.5MB in the beginning and 99.2MB in the end (delta: 12.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.56ms. Allocated memory is still 142.6MB. Free memory was 99.2MB in the beginning and 98.4MB in the end (delta: 827.5kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 24.69ms. Allocated memory is still 142.6MB. Free memory was 98.4MB in the beginning and 96.6MB in the end (delta: 1.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 211.29ms. Allocated memory is still 142.6MB. Free memory was 96.6MB in the beginning and 82.4MB in the end (delta: 14.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 2551.91ms. Allocated memory is still 142.6MB. Free memory was 81.6MB in the beginning and 83.9MB in the end (delta: -2.3MB). Peak memory consumption was 1.4MB. Max. memory is 16.1GB. * Witness Printer took 2.47ms. Allocated memory is still 142.6MB. Free memory was 83.9MB in the beginning and 83.9MB in the end (delta: 37.0kB). 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 - UnprovableResult [Line: 109]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: overapproximation of someBinaryFLOATComparisonOperation at line 98, overapproximation of someBinaryDOUBLEComparisonOperation at line 108, overapproximation of someBinaryArithmeticFLOAToperation at line 92, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 100, overapproximation of someBinaryArithmeticFLOAToperation at line 102. Possible FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -0.6f && IN < 0.6f) [L100] CALL, EXPR f(IN) VAL [\old(x)=111] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=111] [L100] RET, EXPR f(IN) VAL [IN=111] [L100] CALL, EXPR fp(IN) VAL [\old(x)=111] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=111] [L100] RET, EXPR fp(IN) VAL [IN=111] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=110] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=110] [L102] RET, EXPR f(x) VAL [IN=111, x=110] [L102] CALL, EXPR fp(x) VAL [\old(x)=110] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=110] [L102] RET, EXPR fp(x) VAL [IN=111, x=110] [L102] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=111] [L109] reach_error() VAL [IN=111] - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 42 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 2.5s, OverallIterations: 7, TraceHistogramMax: 5, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 0.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 29 SdHoareTripleChecker+Valid, 0.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 25 mSDsluCounter, 1039 SdHoareTripleChecker+Invalid, 0.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 824 mSDsCounter, 20 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 412 IncrementalHoareTripleChecker+Invalid, 432 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 20 mSolverCounterUnsat, 215 mSDtfsCounter, 412 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 136 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=63occurred in iteration=6, InterpolantAutomatonStates: 40, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 9 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 1.0s InterpolantComputationTime, 177 NumberOfCodeBlocks, 173 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 177 ConstructedInterpolants, 0 QuantifiedInterpolants, 896 SizeOfPredicates, 9 NumberOfNonLiveVariables, 252 ConjunctsInSsa, 44 ConjunctsInUnsatCore, 11 InterpolantComputations, 3 PerfectInterpolantSequences, 45/111 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 RESULT: Ultimate could not prove your program: unable to determine feasibility of some traces [2025-02-05 17:30:02,534 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 Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### 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/combinations/gcd_4+newton_2_3.i -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.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 a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 --- Real Ultimate output --- This is Ultimate 0.3.0-?-c00e63d-m [2025-02-05 17:30:04,287 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-02-05 17:30:04,372 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2025-02-05 17:30:04,375 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-02-05 17:30:04,375 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-02-05 17:30:04,425 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-02-05 17:30:04,427 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-02-05 17:30:04,429 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-02-05 17:30:04,431 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-02-05 17:30:04,431 INFO L153 SettingsManager]: * Use memory slicer=true [2025-02-05 17:30:04,432 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-02-05 17:30:04,432 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-02-05 17:30:04,432 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-02-05 17:30:04,432 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-02-05 17:30:04,432 INFO L153 SettingsManager]: * Use SBE=true [2025-02-05 17:30:04,433 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * sizeof long=4 [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-02-05 17:30:04,433 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * sizeof long double=12 [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Use constant arrays=true [2025-02-05 17:30:04,434 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-02-05 17:30:04,434 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 17:30:04,435 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-02-05 17:30:04,435 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-02-05 17:30:04,436 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-02-05 17:30:04,436 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-02-05 17:30:04,436 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-02-05 17:30:04,436 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-02-05 17:30:04,436 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-02-05 17:30:04,436 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 -> a8b52922fdfe93dd417523e4e63c80c50c6631dbe5ff22aa1a5e25c09a617278 [2025-02-05 17:30:04,679 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-02-05 17:30:04,685 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-02-05 17:30:04,687 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-02-05 17:30:04,689 INFO L270 PluginConnector]: Initializing CDTParser... [2025-02-05 17:30:04,689 INFO L274 PluginConnector]: CDTParser initialized [2025-02-05 17:30:04,691 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-02-05 17:30:05,833 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/105420b9e/2f2833ca3fc84f55ba2a3af3079ab177/FLAG49ea44836 [2025-02-05 17:30:06,031 INFO L384 CDTParser]: Found 1 translation units. [2025-02-05 17:30:06,032 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_2_3.i [2025-02-05 17:30:06,038 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/105420b9e/2f2833ca3fc84f55ba2a3af3079ab177/FLAG49ea44836 [2025-02-05 17:30:06,051 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/105420b9e/2f2833ca3fc84f55ba2a3af3079ab177 [2025-02-05 17:30:06,053 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-02-05 17:30:06,054 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-02-05 17:30:06,054 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-02-05 17:30:06,055 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-02-05 17:30:06,057 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-02-05 17:30:06,058 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,058 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@69ea14cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06, skipping insertion in model container [2025-02-05 17:30:06,059 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,068 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-02-05 17:30:06,182 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/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-02-05 17:30:06,208 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/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-02-05 17:30:06,208 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 17:30:06,221 INFO L200 MainTranslator]: Completed pre-run [2025-02-05 17:30:06,232 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/combinations/gcd_4+newton_2_3.i[1224,1237] [2025-02-05 17:30:06,244 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/combinations/gcd_4+newton_2_3.i[2827,2840] [2025-02-05 17:30:06,245 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-02-05 17:30:06,261 INFO L204 MainTranslator]: Completed translation [2025-02-05 17:30:06,262 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06 WrapperNode [2025-02-05 17:30:06,263 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-02-05 17:30:06,263 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-02-05 17:30:06,264 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-02-05 17:30:06,264 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-02-05 17:30:06,269 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,279 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,293 INFO L138 Inliner]: procedures = 28, calls = 26, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 73 [2025-02-05 17:30:06,294 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-02-05 17:30:06,294 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-02-05 17:30:06,294 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-02-05 17:30:06,294 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-02-05 17:30:06,300 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,301 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,302 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,313 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2025-02-05 17:30:06,313 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,313 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,318 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,322 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,323 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,326 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,328 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-02-05 17:30:06,328 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-02-05 17:30:06,328 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-02-05 17:30:06,328 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-02-05 17:30:06,329 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (1/1) ... [2025-02-05 17:30:06,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-02-05 17:30:06,344 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:06,354 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-02-05 17:30:06,359 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-02-05 17:30:06,379 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-02-05 17:30:06,379 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-02-05 17:30:06,380 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-02-05 17:30:06,380 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-02-05 17:30:06,380 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-02-05 17:30:06,380 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-02-05 17:30:06,380 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-02-05 17:30:06,380 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-02-05 17:30:06,380 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-02-05 17:30:06,380 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-02-05 17:30:06,381 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-02-05 17:30:06,425 INFO L257 CfgBuilder]: Building ICFG [2025-02-05 17:30:06,427 INFO L287 CfgBuilder]: Building CFG for each procedure with an implementation [2025-02-05 17:30:19,382 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2025-02-05 17:30:19,382 INFO L308 CfgBuilder]: Performing block encoding [2025-02-05 17:30:19,390 INFO L332 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-02-05 17:30:19,390 INFO L337 CfgBuilder]: Removed 0 assume(true) statements. [2025-02-05 17:30:19,390 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 05:30:19 BoogieIcfgContainer [2025-02-05 17:30:19,390 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-02-05 17:30:19,396 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-02-05 17:30:19,396 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-02-05 17:30:19,399 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-02-05 17:30:19,399 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.02 05:30:06" (1/3) ... [2025-02-05 17:30:19,399 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@76311eaf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 05:30:19, skipping insertion in model container [2025-02-05 17:30:19,400 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.02 05:30:06" (2/3) ... [2025-02-05 17:30:19,400 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@76311eaf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.02 05:30:19, skipping insertion in model container [2025-02-05 17:30:19,400 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 05.02 05:30:19" (3/3) ... [2025-02-05 17:30:19,401 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_2_3.i [2025-02-05 17:30:19,410 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-02-05 17:30:19,412 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_2_3.i that has 4 procedures, 42 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-02-05 17:30:19,447 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-02-05 17:30:19,457 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;@4175143c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-02-05 17:30:19,457 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-02-05 17:30:19,460 INFO L276 IsEmpty]: Start isEmpty. Operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-02-05 17:30:19,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-02-05 17:30:19,463 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:19,464 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:19,464 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:19,468 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:19,468 INFO L85 PathProgramCache]: Analyzing trace with hash -1151646490, now seen corresponding path program 1 times [2025-02-05 17:30:19,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:30:19,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [278674718] [2025-02-05 17:30:19,474 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:19,475 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:19,475 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:19,477 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:19,478 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-02-05 17:30:19,519 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-02-05 17:30:19,535 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-02-05 17:30:19,535 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:19,535 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:19,538 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-05 17:30:19,541 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:19,628 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:19,629 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 17:30:19,629 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-02-05 17:30:19,629 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [278674718] [2025-02-05 17:30:19,629 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [278674718] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 17:30:19,630 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 17:30:19,630 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-05 17:30:19,631 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [75398024] [2025-02-05 17:30:19,631 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 17:30:19,633 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-05 17:30:19,633 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-02-05 17:30:19,646 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-05 17:30:19,648 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:19,650 INFO L87 Difference]: Start difference. First operand has 42 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 31 states have internal predecessors, (40), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:19,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:19,774 INFO L93 Difference]: Finished difference Result 81 states and 107 transitions. [2025-02-05 17:30:19,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-05 17:30:19,777 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2025-02-05 17:30:19,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:19,796 INFO L225 Difference]: With dead ends: 81 [2025-02-05 17:30:19,796 INFO L226 Difference]: Without dead ends: 37 [2025-02-05 17:30:19,805 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:19,810 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 6 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:19,811 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 84 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-05 17:30:19,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-02-05 17:30:19,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 35. [2025-02-05 17:30:19,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:19,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 41 transitions. [2025-02-05 17:30:19,851 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 41 transitions. Word has length 11 [2025-02-05 17:30:19,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:19,851 INFO L471 AbstractCegarLoop]: Abstraction has 35 states and 41 transitions. [2025-02-05 17:30:19,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:19,851 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 41 transitions. [2025-02-05 17:30:19,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-02-05 17:30:19,852 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:19,852 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:19,860 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-02-05 17:30:20,053 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 [2025-02-05 17:30:20,054 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:20,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:20,055 INFO L85 PathProgramCache]: Analyzing trace with hash 2048670773, now seen corresponding path program 1 times [2025-02-05 17:30:20,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:30:20,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1959273343] [2025-02-05 17:30:20,056 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:20,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:20,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:20,058 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:20,059 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-02-05 17:30:20,086 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-02-05 17:30:20,101 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-02-05 17:30:20,102 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:20,102 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:20,105 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-02-05 17:30:20,106 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:20,187 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:20,187 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-02-05 17:30:20,187 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-02-05 17:30:20,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1959273343] [2025-02-05 17:30:20,187 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1959273343] provided 1 perfect and 0 imperfect interpolant sequences [2025-02-05 17:30:20,187 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-02-05 17:30:20,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-02-05 17:30:20,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [163861930] [2025-02-05 17:30:20,188 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-02-05 17:30:20,189 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-02-05 17:30:20,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-02-05 17:30:20,189 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-02-05 17:30:20,189 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:20,189 INFO L87 Difference]: Start difference. First operand 35 states and 41 transitions. Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:20,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:20,294 INFO L93 Difference]: Finished difference Result 50 states and 61 transitions. [2025-02-05 17:30:20,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-02-05 17:30:20,295 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2025-02-05 17:30:20,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:20,296 INFO L225 Difference]: With dead ends: 50 [2025-02-05 17:30:20,296 INFO L226 Difference]: Without dead ends: 37 [2025-02-05 17:30:20,296 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-02-05 17:30:20,297 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 4 mSDsluCounter, 31 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:20,297 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 67 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-02-05 17:30:20,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2025-02-05 17:30:20,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2025-02-05 17:30:20,300 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:20,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2025-02-05 17:30:20,301 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 12 [2025-02-05 17:30:20,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:20,301 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2025-02-05 17:30:20,301 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:20,301 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2025-02-05 17:30:20,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-02-05 17:30:20,302 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:20,302 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:20,309 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-02-05 17:30:20,502 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:20,502 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:20,503 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:20,503 INFO L85 PathProgramCache]: Analyzing trace with hash 373208147, now seen corresponding path program 1 times [2025-02-05 17:30:20,503 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:30:20,503 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [803860745] [2025-02-05 17:30:20,503 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:20,503 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:20,503 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:20,507 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:20,508 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-02-05 17:30:20,550 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-02-05 17:30:20,569 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-02-05 17:30:20,569 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:20,570 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:20,573 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-02-05 17:30:20,576 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:20,953 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:20,953 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:21,221 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:21,221 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-02-05 17:30:21,221 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [803860745] [2025-02-05 17:30:21,221 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [803860745] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:21,221 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 17:30:21,221 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2025-02-05 17:30:21,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [98904224] [2025-02-05 17:30:21,222 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:21,222 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-02-05 17:30:21,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-02-05 17:30:21,222 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-02-05 17:30:21,222 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2025-02-05 17:30:21,223 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:21,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:21,586 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2025-02-05 17:30:21,587 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-02-05 17:30:21,587 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2025-02-05 17:30:21,587 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:21,587 INFO L225 Difference]: With dead ends: 54 [2025-02-05 17:30:21,588 INFO L226 Difference]: Without dead ends: 42 [2025-02-05 17:30:21,588 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2025-02-05 17:30:21,588 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:21,588 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 127 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-02-05 17:30:21,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-02-05 17:30:21,592 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2025-02-05 17:30:21,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:21,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2025-02-05 17:30:21,592 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 14 [2025-02-05 17:30:21,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:21,593 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2025-02-05 17:30:21,593 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:21,593 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2025-02-05 17:30:21,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-02-05 17:30:21,593 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:21,593 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:21,604 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-02-05 17:30:21,794 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:21,795 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:21,795 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:21,795 INFO L85 PathProgramCache]: Analyzing trace with hash 1716297167, now seen corresponding path program 1 times [2025-02-05 17:30:21,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:30:21,796 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [185405034] [2025-02-05 17:30:21,796 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:30:21,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:21,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:21,800 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:21,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-02-05 17:30:21,826 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-02-05 17:30:21,842 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-02-05 17:30:21,842 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-02-05 17:30:21,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:21,845 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-02-05 17:30:21,846 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:22,608 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:22,612 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:23,301 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-02-05 17:30:23,301 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-02-05 17:30:23,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [185405034] [2025-02-05 17:30:23,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [185405034] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:23,302 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 17:30:23,302 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2025-02-05 17:30:23,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [711338214] [2025-02-05 17:30:23,302 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:23,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-02-05 17:30:23,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-02-05 17:30:23,303 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-02-05 17:30:23,303 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-02-05 17:30:23,303 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:24,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:30:24,367 INFO L93 Difference]: Finished difference Result 62 states and 76 transitions. [2025-02-05 17:30:24,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2025-02-05 17:30:24,368 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 18 [2025-02-05 17:30:24,368 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:30:24,369 INFO L225 Difference]: With dead ends: 62 [2025-02-05 17:30:24,370 INFO L226 Difference]: Without dead ends: 49 [2025-02-05 17:30:24,371 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2025-02-05 17:30:24,371 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 155 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2025-02-05 17:30:24,371 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 189 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2025-02-05 17:30:24,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2025-02-05 17:30:24,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2025-02-05 17:30:24,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-02-05 17:30:24,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 56 transitions. [2025-02-05 17:30:24,376 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 56 transitions. Word has length 18 [2025-02-05 17:30:24,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:30:24,377 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 56 transitions. [2025-02-05 17:30:24,377 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.8) internal successors, (28), 10 states have internal predecessors, (28), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:24,377 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 56 transitions. [2025-02-05 17:30:24,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-02-05 17:30:24,377 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:30:24,377 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:30:24,384 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-02-05 17:30:24,582 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:24,582 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:30:24,582 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:30:24,582 INFO L85 PathProgramCache]: Analyzing trace with hash 1448466508, now seen corresponding path program 2 times [2025-02-05 17:30:24,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:30:24,583 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [142970345] [2025-02-05 17:30:24,583 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-02-05 17:30:24,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:30:24,583 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-02-05 17:30:24,585 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-02-05 17:30:24,586 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-02-05 17:30:24,616 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 22 statements into 2 equivalence classes. [2025-02-05 17:30:24,637 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 22 of 22 statements. [2025-02-05 17:30:24,637 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-02-05 17:30:24,637 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-02-05 17:30:24,640 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 18 conjuncts are in the unsatisfiable core [2025-02-05 17:30:24,641 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-02-05 17:30:26,550 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-05 17:30:26,551 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-02-05 17:30:36,043 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-02-05 17:30:36,043 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-02-05 17:30:36,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [142970345] [2025-02-05 17:30:36,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [142970345] provided 0 perfect and 2 imperfect interpolant sequences [2025-02-05 17:30:36,043 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-02-05 17:30:36,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 20 [2025-02-05 17:30:36,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1953923852] [2025-02-05 17:30:36,043 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-02-05 17:30:36,043 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2025-02-05 17:30:36,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-02-05 17:30:36,045 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2025-02-05 17:30:36,046 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2025-02-05 17:30:36,046 INFO L87 Difference]: Start difference. First operand 48 states and 56 transitions. Second operand has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:30:51,811 WARN L286 SmtUtils]: Spent 11.37s on a formula simplification that was a NOOP. DAG size: 30 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2025-02-05 17:30:56,334 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-02-05 17:31:00,341 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-02-05 17:31:02,027 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-02-05 17:31:15,036 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.60s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-02-05 17:31:19,405 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2025-02-05 17:31:27,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-02-05 17:31:27,466 INFO L93 Difference]: Finished difference Result 70 states and 86 transitions. [2025-02-05 17:31:27,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2025-02-05 17:31:27,471 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 22 [2025-02-05 17:31:27,472 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-02-05 17:31:27,473 INFO L225 Difference]: With dead ends: 70 [2025-02-05 17:31:27,473 INFO L226 Difference]: Without dead ends: 67 [2025-02-05 17:31:27,474 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 36.6s TimeCoverageRelationStatistics Valid=96, Invalid=503, Unknown=1, NotChecked=0, Total=600 [2025-02-05 17:31:27,474 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 408 mSDsCounter, 0 mSdLazyCounter, 246 mSolverCounterSat, 9 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 22.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 439 SdHoareTripleChecker+Invalid, 258 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 246 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 23.0s IncrementalHoareTripleChecker+Time [2025-02-05 17:31:27,474 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 439 Invalid, 258 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 246 Invalid, 3 Unknown, 0 Unchecked, 23.0s Time] [2025-02-05 17:31:27,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2025-02-05 17:31:27,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 65. [2025-02-05 17:31:27,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 53 states have internal predecessors, (61), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-02-05 17:31:27,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 79 transitions. [2025-02-05 17:31:27,493 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 79 transitions. Word has length 22 [2025-02-05 17:31:27,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-02-05 17:31:27,493 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 79 transitions. [2025-02-05 17:31:27,493 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 1.9444444444444444) internal successors, (35), 18 states have internal predecessors, (35), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-02-05 17:31:27,493 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 79 transitions. [2025-02-05 17:31:27,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-02-05 17:31:27,494 INFO L210 NwaCegarLoop]: Found error trace [2025-02-05 17:31:27,494 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-02-05 17:31:27,517 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-02-05 17:31:27,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-02-05 17:31:27,694 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-02-05 17:31:27,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-02-05 17:31:27,695 INFO L85 PathProgramCache]: Analyzing trace with hash 1155762721, now seen corresponding path program 1 times [2025-02-05 17:31:27,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-02-05 17:31:27,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [988028286] [2025-02-05 17:31:27,695 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-02-05 17:31:27,695 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2025-02-05 17:31:27,695 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/mathsat [2025-02-05 17:31:27,698 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2025-02-05 17:31:27,699 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2025-02-05 17:31:27,727 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes.