./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/combinations/gcd_4+newton_3_8.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/combinations/gcd_4+newton_3_8.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 5e702e85c3d7f91108386d3bed8993d879aa98d42d10adbcd14f5fa9bf29e29b --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 05:40:30,487 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 05:40:30,558 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-09 05:40:30,563 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 05:40:30,564 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 05:40:30,599 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 05:40:30,600 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 05:40:30,600 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 05:40:30,601 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 05:40:30,601 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 05:40:30,601 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 05:40:30,601 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 05:40:30,601 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 05:40:30,601 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 05:40:30,601 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 05:40:30,602 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 05:40:30,602 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 05:40:30,602 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 05:40:30,603 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 05:40:30,603 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 05:40:30,603 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 05:40:30,604 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 05:40:30,605 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 05:40:30,605 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 05:40:30,605 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 05:40:30,605 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 05:40:30,605 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 05:40:30,605 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:30,606 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 05:40:30,606 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 05:40:30,606 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 05:40:30,606 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 05:40:30,606 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:30,606 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 05:40:30,606 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 05:40:30,607 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 05:40:30,608 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 05:40:30,608 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 05:40:30,608 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 -> 5e702e85c3d7f91108386d3bed8993d879aa98d42d10adbcd14f5fa9bf29e29b [2025-01-09 05:40:30,930 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 05:40:30,941 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 05:40:30,944 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 05:40:30,945 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 05:40:30,945 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 05:40:30,947 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_3_8.i [2025-01-09 05:40:32,360 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/553f50a5d/b29c1bb7c4a64fc69b78feeaa58160a8/FLAG57e9f4ce3 [2025-01-09 05:40:32,624 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 05:40:32,625 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_3_8.i [2025-01-09 05:40:32,632 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/553f50a5d/b29c1bb7c4a64fc69b78feeaa58160a8/FLAG57e9f4ce3 [2025-01-09 05:40:32,645 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/553f50a5d/b29c1bb7c4a64fc69b78feeaa58160a8 [2025-01-09 05:40:32,648 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 05:40:32,649 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 05:40:32,650 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 05:40:32,651 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 05:40:32,654 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 05:40:32,655 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,656 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@184cb39e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32, skipping insertion in model container [2025-01-09 05:40:32,656 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,669 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 05:40:32,812 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_3_8.i[1224,1237] [2025-01-09 05:40:32,847 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_3_8.i[2848,2861] [2025-01-09 05:40:32,850 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 05:40:32,860 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 05:40:32,872 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_3_8.i[1224,1237] [2025-01-09 05:40:32,886 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_3_8.i[2848,2861] [2025-01-09 05:40:32,887 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 05:40:32,905 INFO L204 MainTranslator]: Completed translation [2025-01-09 05:40:32,907 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32 WrapperNode [2025-01-09 05:40:32,907 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 05:40:32,908 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 05:40:32,908 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 05:40:32,908 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 05:40:32,915 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,921 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,938 INFO L138 Inliner]: procedures = 27, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 81 [2025-01-09 05:40:32,940 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 05:40:32,942 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 05:40:32,942 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 05:40:32,942 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 05:40:32,949 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,949 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,951 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,966 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-01-09 05:40:32,970 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,970 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,974 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,978 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,982 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,982 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,983 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,985 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 05:40:32,986 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 05:40:32,986 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 05:40:32,986 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 05:40:32,987 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (1/1) ... [2025-01-09 05:40:32,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:33,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:33,015 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-01-09 05:40:33,017 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-01-09 05:40:33,035 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 05:40:33,035 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-01-09 05:40:33,036 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-01-09 05:40:33,036 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-01-09 05:40:33,036 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-01-09 05:40:33,036 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 05:40:33,036 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-09 05:40:33,036 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 05:40:33,036 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 05:40:33,036 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 05:40:33,036 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 05:40:33,093 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 05:40:33,095 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 05:40:33,277 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2025-01-09 05:40:33,277 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 05:40:33,289 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 05:40:33,291 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-09 05:40:33,291 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:40:33 BoogieIcfgContainer [2025-01-09 05:40:33,291 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 05:40:33,294 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 05:40:33,295 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 05:40:33,299 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 05:40:33,299 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 05:40:32" (1/3) ... [2025-01-09 05:40:33,300 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e77330f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:40:33, skipping insertion in model container [2025-01-09 05:40:33,300 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:32" (2/3) ... [2025-01-09 05:40:33,300 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e77330f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:40:33, skipping insertion in model container [2025-01-09 05:40:33,301 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:40:33" (3/3) ... [2025-01-09 05:40:33,302 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_8.i [2025-01-09 05:40:33,316 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 05:40:33,317 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_8.i that has 4 procedures, 45 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-01-09 05:40:33,366 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 05:40:33,377 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;@22306c7d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 05:40:33,378 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-01-09 05:40:33,381 INFO L276 IsEmpty]: Start isEmpty. Operand has 45 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 32 states have internal predecessors, (41), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-01-09 05:40:33,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-01-09 05:40:33,387 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:33,387 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:33,389 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:33,393 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:33,393 INFO L85 PathProgramCache]: Analyzing trace with hash -1787067343, now seen corresponding path program 1 times [2025-01-09 05:40:33,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:33,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [235720889] [2025-01-09 05:40:33,403 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:33,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:33,462 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-01-09 05:40:33,481 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-01-09 05:40:33,481 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:33,481 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:33,652 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:33,654 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:33,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [235720889] [2025-01-09 05:40:33,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [235720889] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 05:40:33,655 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 05:40:33,655 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-09 05:40:33,657 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [397701359] [2025-01-09 05:40:33,657 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 05:40:33,661 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-09 05:40:33,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:33,675 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-09 05:40:33,676 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-09 05:40:33,677 INFO L87 Difference]: Start difference. First operand has 45 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 32 states have internal predecessors, (41), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) 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-01-09 05:40:33,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:33,721 INFO L93 Difference]: Finished difference Result 87 states and 117 transitions. [2025-01-09 05:40:33,723 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-09 05:40:33,725 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-01-09 05:40:33,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:33,729 INFO L225 Difference]: With dead ends: 87 [2025-01-09 05:40:33,729 INFO L226 Difference]: Without dead ends: 40 [2025-01-09 05:40:33,731 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-01-09 05:40:33,734 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:33,735 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 93 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 05:40:33,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-01-09 05:40:33,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 38. [2025-01-09 05:40:33,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:33,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2025-01-09 05:40:33,766 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 11 [2025-01-09 05:40:33,766 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:33,766 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2025-01-09 05:40:33,766 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-01-09 05:40:33,767 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2025-01-09 05:40:33,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-01-09 05:40:33,769 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:33,769 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:33,770 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-09 05:40:33,770 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:33,771 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:33,771 INFO L85 PathProgramCache]: Analyzing trace with hash -1509370903, now seen corresponding path program 1 times [2025-01-09 05:40:33,771 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:33,771 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1367001123] [2025-01-09 05:40:33,771 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:33,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:33,782 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-01-09 05:40:33,791 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-01-09 05:40:33,791 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:33,791 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:33,866 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:33,867 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:33,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1367001123] [2025-01-09 05:40:33,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1367001123] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 05:40:33,867 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 05:40:33,867 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-09 05:40:33,867 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [603240352] [2025-01-09 05:40:33,867 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 05:40:33,868 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-09 05:40:33,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:33,869 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-09 05:40:33,869 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-09 05:40:33,869 INFO L87 Difference]: Start difference. First operand 38 states and 46 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-01-09 05:40:33,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:33,894 INFO L93 Difference]: Finished difference Result 53 states and 66 transitions. [2025-01-09 05:40:33,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-09 05:40:33,894 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-01-09 05:40:33,894 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:33,895 INFO L225 Difference]: With dead ends: 53 [2025-01-09 05:40:33,895 INFO L226 Difference]: Without dead ends: 40 [2025-01-09 05:40:33,895 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-01-09 05:40:33,896 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 77 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-01-09 05:40:33,896 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 77 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 05:40:33,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-01-09 05:40:33,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2025-01-09 05:40:33,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 26 states have (on average 1.1923076923076923) internal successors, (31), 28 states have internal predecessors, (31), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:33,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2025-01-09 05:40:33,902 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 12 [2025-01-09 05:40:33,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:33,903 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2025-01-09 05:40:33,903 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-01-09 05:40:33,903 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2025-01-09 05:40:33,904 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-01-09 05:40:33,905 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:33,905 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:33,905 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-01-09 05:40:33,905 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:33,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:33,906 INFO L85 PathProgramCache]: Analyzing trace with hash -1983253012, now seen corresponding path program 1 times [2025-01-09 05:40:33,906 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:33,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1745754146] [2025-01-09 05:40:33,909 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:33,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:33,916 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-01-09 05:40:33,922 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-01-09 05:40:33,922 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:33,922 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:34,041 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:34,041 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:34,041 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1745754146] [2025-01-09 05:40:34,041 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1745754146] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 05:40:34,041 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 05:40:34,041 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-09 05:40:34,041 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [957468919] [2025-01-09 05:40:34,041 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 05:40:34,042 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-09 05:40:34,042 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:34,043 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-09 05:40:34,043 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-09 05:40:34,044 INFO L87 Difference]: Start difference. First operand 40 states and 48 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-01-09 05:40:34,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:34,070 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2025-01-09 05:40:34,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-09 05:40:34,071 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-01-09 05:40:34,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:34,072 INFO L225 Difference]: With dead ends: 54 [2025-01-09 05:40:34,072 INFO L226 Difference]: Without dead ends: 42 [2025-01-09 05:40:34,072 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-01-09 05:40:34,073 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 76 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-01-09 05:40:34,073 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 76 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 05:40:34,073 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2025-01-09 05:40:34,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2025-01-09 05:40:34,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 30 states have internal predecessors, (33), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:34,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2025-01-09 05:40:34,083 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 14 [2025-01-09 05:40:34,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:34,083 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2025-01-09 05:40:34,084 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-01-09 05:40:34,084 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2025-01-09 05:40:34,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2025-01-09 05:40:34,084 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:34,084 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:34,085 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-01-09 05:40:34,085 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:34,085 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:34,085 INFO L85 PathProgramCache]: Analyzing trace with hash 1890509551, now seen corresponding path program 1 times [2025-01-09 05:40:34,086 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:34,086 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1077311592] [2025-01-09 05:40:34,086 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:34,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:34,092 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-01-09 05:40:34,109 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-01-09 05:40:34,110 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:34,110 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:34,249 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:34,250 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:34,250 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1077311592] [2025-01-09 05:40:34,250 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1077311592] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 05:40:34,250 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1357397192] [2025-01-09 05:40:34,250 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:34,250 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:34,250 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:34,255 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:34,257 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 05:40:34,298 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 16 statements into 1 equivalence classes. [2025-01-09 05:40:34,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 16 of 16 statements. [2025-01-09 05:40:34,320 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:34,320 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:34,321 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2025-01-09 05:40:34,325 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:34,434 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:34,437 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:34,527 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:34,528 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1357397192] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:34,529 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 05:40:34,529 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5, 5] total 10 [2025-01-09 05:40:34,529 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [350314425] [2025-01-09 05:40:34,529 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:34,530 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 05:40:34,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:34,530 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 05:40:34,531 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2025-01-09 05:40:34,532 INFO L87 Difference]: Start difference. First operand 42 states and 50 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-01-09 05:40:34,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:34,594 INFO L93 Difference]: Finished difference Result 58 states and 71 transitions. [2025-01-09 05:40:34,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 05:40:34,597 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-01-09 05:40:34,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:34,598 INFO L225 Difference]: With dead ends: 58 [2025-01-09 05:40:34,598 INFO L226 Difference]: Without dead ends: 46 [2025-01-09 05:40:34,598 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-01-09 05:40:34,599 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 220 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:34,599 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 220 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 05:40:34,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2025-01-09 05:40:34,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2025-01-09 05:40:34,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 32 states have (on average 1.15625) internal successors, (37), 34 states have internal predecessors, (37), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:34,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 54 transitions. [2025-01-09 05:40:34,607 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 54 transitions. Word has length 16 [2025-01-09 05:40:34,607 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:34,607 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 54 transitions. [2025-01-09 05:40:34,607 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-01-09 05:40:34,607 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 54 transitions. [2025-01-09 05:40:34,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-01-09 05:40:34,608 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:34,608 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:34,615 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-01-09 05:40:34,808 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-01-09 05:40:34,809 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:34,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:34,809 INFO L85 PathProgramCache]: Analyzing trace with hash 316493493, now seen corresponding path program 2 times [2025-01-09 05:40:34,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:34,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561507911] [2025-01-09 05:40:34,809 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 05:40:34,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:34,816 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-01-09 05:40:34,832 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-01-09 05:40:34,832 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 05:40:34,832 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:35,023 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:35,024 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:35,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1561507911] [2025-01-09 05:40:35,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1561507911] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 05:40:35,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1389694609] [2025-01-09 05:40:35,024 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 05:40:35,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:35,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:35,027 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:35,030 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 05:40:35,062 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-01-09 05:40:35,082 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-01-09 05:40:35,082 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 05:40:35,082 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:35,085 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-01-09 05:40:35,087 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:35,224 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:35,224 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:35,312 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:35,313 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1389694609] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:35,313 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 05:40:35,313 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2025-01-09 05:40:35,313 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1420455584] [2025-01-09 05:40:35,313 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:35,313 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2025-01-09 05:40:35,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:35,314 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2025-01-09 05:40:35,314 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=175, Unknown=0, NotChecked=0, Total=272 [2025-01-09 05:40:35,314 INFO L87 Difference]: Start difference. First operand 46 states and 54 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-01-09 05:40:35,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:35,459 INFO L93 Difference]: Finished difference Result 67 states and 86 transitions. [2025-01-09 05:40:35,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 05:40:35,461 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-01-09 05:40:35,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:35,462 INFO L225 Difference]: With dead ends: 67 [2025-01-09 05:40:35,462 INFO L226 Difference]: Without dead ends: 53 [2025-01-09 05:40:35,463 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=121, Invalid=221, Unknown=0, NotChecked=0, Total=342 [2025-01-09 05:40:35,463 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 252 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 291 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:35,464 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 291 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 05:40:35,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2025-01-09 05:40:35,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 51. [2025-01-09 05:40:35,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 37 states have (on average 1.135135135135135) internal successors, (42), 39 states have internal predecessors, (42), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:35,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2025-01-09 05:40:35,480 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 20 [2025-01-09 05:40:35,480 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:35,480 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2025-01-09 05:40:35,480 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-01-09 05:40:35,481 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2025-01-09 05:40:35,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-01-09 05:40:35,481 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:35,481 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:35,491 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-01-09 05:40:35,682 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-01-09 05:40:35,682 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:35,683 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:35,683 INFO L85 PathProgramCache]: Analyzing trace with hash 718801786, now seen corresponding path program 3 times [2025-01-09 05:40:35,683 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:35,683 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [723806778] [2025-01-09 05:40:35,683 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 05:40:35,683 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:35,693 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-01-09 05:40:35,716 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 22 of 22 statements. [2025-01-09 05:40:35,716 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-09 05:40:35,717 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 05:40:35,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1048671794] [2025-01-09 05:40:35,719 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 05:40:35,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:35,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:35,721 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:35,725 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 05:40:35,751 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-01-09 05:40:35,768 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 18 of 22 statements. [2025-01-09 05:40:35,768 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-01-09 05:40:35,768 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:35,771 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-01-09 05:40:35,773 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:35,940 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 05:40:35,940 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:36,286 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-09 05:40:36,287 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:36,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [723806778] [2025-01-09 05:40:36,287 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 05:40:36,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1048671794] [2025-01-09 05:40:36,288 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1048671794] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:36,288 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:40:36,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2025-01-09 05:40:36,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1390366793] [2025-01-09 05:40:36,288 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:36,288 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-09 05:40:36,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:36,289 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-09 05:40:36,289 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2025-01-09 05:40:36,290 INFO L87 Difference]: Start difference. First operand 51 states and 59 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-01-09 05:40:36,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:36,564 INFO L93 Difference]: Finished difference Result 72 states and 88 transitions. [2025-01-09 05:40:36,564 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-01-09 05:40:36,565 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-01-09 05:40:36,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:36,566 INFO L225 Difference]: With dead ends: 72 [2025-01-09 05:40:36,568 INFO L226 Difference]: Without dead ends: 69 [2025-01-09 05:40:36,568 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-01-09 05:40:36,569 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 8 mSDsluCounter, 357 mSDsCounter, 0 mSdLazyCounter, 211 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 223 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 211 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:36,569 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 391 Invalid, 223 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 211 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 05:40:36,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2025-01-09 05:40:36,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 66. [2025-01-09 05:40:36,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 48 states have (on average 1.2083333333333333) internal successors, (58), 52 states have internal predecessors, (58), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 05:40:36,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 80 transitions. [2025-01-09 05:40:36,579 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 80 transitions. Word has length 22 [2025-01-09 05:40:36,579 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:36,579 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 80 transitions. [2025-01-09 05:40:36,579 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-01-09 05:40:36,579 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 80 transitions. [2025-01-09 05:40:36,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2025-01-09 05:40:36,581 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:36,581 INFO L218 NwaCegarLoop]: trace histogram [6, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:36,589 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-01-09 05:40:36,785 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-01-09 05:40:36,785 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:36,786 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:36,786 INFO L85 PathProgramCache]: Analyzing trace with hash 790014719, now seen corresponding path program 4 times [2025-01-09 05:40:36,786 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:36,786 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1576355653] [2025-01-09 05:40:36,786 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-09 05:40:36,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:36,791 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 24 statements into 2 equivalence classes. [2025-01-09 05:40:36,803 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-01-09 05:40:36,803 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-01-09 05:40:36,803 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:36,933 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 6 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:36,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:36,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1576355653] [2025-01-09 05:40:36,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1576355653] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 05:40:36,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [991424929] [2025-01-09 05:40:36,934 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-09 05:40:36,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:36,934 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:36,938 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:36,939 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 05:40:36,970 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 24 statements into 2 equivalence classes. [2025-01-09 05:40:36,985 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 24 of 24 statements. [2025-01-09 05:40:36,986 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-01-09 05:40:36,986 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:36,989 INFO L256 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-01-09 05:40:36,991 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:37,161 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 2 proven. 34 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:37,162 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:37,320 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:37,321 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [991424929] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:37,321 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 05:40:37,321 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 9] total 22 [2025-01-09 05:40:37,321 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380216896] [2025-01-09 05:40:37,321 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:37,322 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-01-09 05:40:37,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:37,323 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-01-09 05:40:37,323 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2025-01-09 05:40:37,323 INFO L87 Difference]: Start difference. First operand 66 states and 80 transitions. Second operand has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 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-01-09 05:40:37,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:37,513 INFO L93 Difference]: Finished difference Result 86 states and 104 transitions. [2025-01-09 05:40:37,514 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 05:40:37,514 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 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 24 [2025-01-09 05:40:37,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:37,515 INFO L225 Difference]: With dead ends: 86 [2025-01-09 05:40:37,515 INFO L226 Difference]: Without dead ends: 59 [2025-01-09 05:40:37,516 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 115 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=174, Invalid=528, Unknown=0, NotChecked=0, Total=702 [2025-01-09 05:40:37,516 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 12 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 434 SdHoareTripleChecker+Invalid, 146 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:37,516 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 434 Invalid, 146 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 05:40:37,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2025-01-09 05:40:37,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2025-01-09 05:40:37,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 42 states have (on average 1.119047619047619) internal successors, (47), 45 states have internal predecessors, (47), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-01-09 05:40:37,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 67 transitions. [2025-01-09 05:40:37,528 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 67 transitions. Word has length 24 [2025-01-09 05:40:37,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:37,528 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 67 transitions. [2025-01-09 05:40:37,528 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 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-01-09 05:40:37,528 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 67 transitions. [2025-01-09 05:40:37,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-01-09 05:40:37,529 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:37,529 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:37,538 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-01-09 05:40:37,730 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,SelfDestructingSolverStorable6 [2025-01-09 05:40:37,730 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:37,731 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:37,731 INFO L85 PathProgramCache]: Analyzing trace with hash -2015702026, now seen corresponding path program 1 times [2025-01-09 05:40:37,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:37,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842533449] [2025-01-09 05:40:37,731 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:37,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:37,736 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-01-09 05:40:37,750 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-01-09 05:40:37,751 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:37,751 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 05:40:37,752 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1055859178] [2025-01-09 05:40:37,752 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:37,752 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:37,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:37,754 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:37,757 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-01-09 05:40:37,785 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-01-09 05:40:37,801 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-01-09 05:40:37,801 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:37,801 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:37,802 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-01-09 05:40:37,804 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:37,948 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 05:40:37,948 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:38,251 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 05:40:38,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:38,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842533449] [2025-01-09 05:40:38,252 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 05:40:38,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1055859178] [2025-01-09 05:40:38,252 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1055859178] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:38,252 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:40:38,252 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2025-01-09 05:40:38,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [712830896] [2025-01-09 05:40:38,252 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:38,253 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2025-01-09 05:40:38,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:38,254 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2025-01-09 05:40:38,254 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2025-01-09 05:40:38,254 INFO L87 Difference]: Start difference. First operand 59 states and 67 transitions. Second operand has 16 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 15 states have internal predecessors, (36), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 05:40:38,464 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:38,464 INFO L93 Difference]: Finished difference Result 65 states and 72 transitions. [2025-01-09 05:40:38,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-01-09 05:40:38,467 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 15 states have internal predecessors, (36), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2025-01-09 05:40:38,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:38,467 INFO L225 Difference]: With dead ends: 65 [2025-01-09 05:40:38,467 INFO L226 Difference]: Without dead ends: 51 [2025-01-09 05:40:38,468 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2025-01-09 05:40:38,468 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 466 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 504 SdHoareTripleChecker+Invalid, 228 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:38,469 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 504 Invalid, 228 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-01-09 05:40:38,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2025-01-09 05:40:38,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2025-01-09 05:40:38,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 37 states have (on average 1.1081081081081081) internal successors, (41), 39 states have internal predecessors, (41), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:38,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 58 transitions. [2025-01-09 05:40:38,482 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 58 transitions. Word has length 27 [2025-01-09 05:40:38,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:38,482 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 58 transitions. [2025-01-09 05:40:38,482 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 15 states have internal predecessors, (36), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 05:40:38,482 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 58 transitions. [2025-01-09 05:40:38,483 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-01-09 05:40:38,483 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:38,483 INFO L218 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:38,491 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2025-01-09 05:40:38,687 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:38,687 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:38,687 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:38,687 INFO L85 PathProgramCache]: Analyzing trace with hash -194897982, now seen corresponding path program 5 times [2025-01-09 05:40:38,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:38,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1635379432] [2025-01-09 05:40:38,688 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-09 05:40:38,688 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:38,692 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 26 statements into 8 equivalence classes. [2025-01-09 05:40:38,698 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 26 of 26 statements. [2025-01-09 05:40:38,699 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-01-09 05:40:38,699 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:38,791 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 25 proven. 20 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 05:40:38,791 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 05:40:38,791 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1635379432] [2025-01-09 05:40:38,792 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1635379432] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-09 05:40:38,792 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1124148257] [2025-01-09 05:40:38,792 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2025-01-09 05:40:38,792 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:38,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:38,794 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:38,797 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-01-09 05:40:38,823 INFO L108 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 partitioned 26 statements into 8 equivalence classes. [2025-01-09 05:40:38,837 INFO L111 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) and asserted 26 of 26 statements. [2025-01-09 05:40:38,838 INFO L114 AnnotateAndAsserter]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2025-01-09 05:40:38,838 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:38,839 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-01-09 05:40:38,840 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:39,024 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 37 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:39,025 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:40:39,165 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:39,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1124148257] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:40:39,165 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-09 05:40:39,165 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 10] total 23 [2025-01-09 05:40:39,165 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [130048240] [2025-01-09 05:40:39,165 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-09 05:40:39,166 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2025-01-09 05:40:39,166 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 05:40:39,167 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2025-01-09 05:40:39,167 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=384, Unknown=0, NotChecked=0, Total=506 [2025-01-09 05:40:39,167 INFO L87 Difference]: Start difference. First operand 51 states and 58 transitions. Second operand has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 23 states have internal predecessors, (61), 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-01-09 05:40:39,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:39,239 INFO L93 Difference]: Finished difference Result 51 states and 58 transitions. [2025-01-09 05:40:39,239 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-09 05:40:39,240 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 23 states have internal predecessors, (61), 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 26 [2025-01-09 05:40:39,241 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:39,241 INFO L225 Difference]: With dead ends: 51 [2025-01-09 05:40:39,241 INFO L226 Difference]: Without dead ends: 23 [2025-01-09 05:40:39,242 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=142, Invalid=410, Unknown=0, NotChecked=0, Total=552 [2025-01-09 05:40:39,242 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 0 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 391 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 05:40:39,242 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 391 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 05:40:39,243 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2025-01-09 05:40:39,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2025-01-09 05:40:39,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.0) internal successors, (14), 14 states have internal predecessors, (14), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-01-09 05:40:39,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2025-01-09 05:40:39,246 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 26 [2025-01-09 05:40:39,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:39,247 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2025-01-09 05:40:39,247 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.652173913043478) internal successors, (61), 23 states have internal predecessors, (61), 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-01-09 05:40:39,247 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2025-01-09 05:40:39,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2025-01-09 05:40:39,249 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:39,249 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:39,257 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-01-09 05:40:39,449 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2025-01-09 05:40:39,450 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:39,450 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:39,450 INFO L85 PathProgramCache]: Analyzing trace with hash 1996948111, now seen corresponding path program 1 times [2025-01-09 05:40:39,450 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 05:40:39,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [707353140] [2025-01-09 05:40:39,451 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:39,451 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 05:40:39,454 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-01-09 05:40:39,457 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-01-09 05:40:39,457 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:39,457 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-09 05:40:39,457 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-01-09 05:40:39,459 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 34 statements into 1 equivalence classes. [2025-01-09 05:40:39,460 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 34 of 34 statements. [2025-01-09 05:40:39,461 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:39,461 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-01-09 05:40:39,479 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-01-09 05:40:39,482 INFO L340 BasicCegarLoop]: Counterexample is feasible [2025-01-09 05:40:39,483 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2025-01-09 05:40:39,485 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2025-01-09 05:40:39,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2025-01-09 05:40:39,487 INFO L422 BasicCegarLoop]: Path program histogram: [5, 1, 1, 1, 1, 1] [2025-01-09 05:40:39,504 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-01-09 05:40:39,506 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.01 05:40:39 BoogieIcfgContainer [2025-01-09 05:40:39,508 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-01-09 05:40:39,508 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-01-09 05:40:39,509 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-01-09 05:40:39,509 INFO L274 PluginConnector]: Witness Printer initialized [2025-01-09 05:40:39,509 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:40:33" (3/4) ... [2025-01-09 05:40:39,511 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-01-09 05:40:39,512 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-01-09 05:40:39,514 INFO L158 Benchmark]: Toolchain (without parser) took 6864.57ms. Allocated memory is still 142.6MB. Free memory was 112.7MB in the beginning and 88.2MB in the end (delta: 24.5MB). Peak memory consumption was 26.6MB. Max. memory is 16.1GB. [2025-01-09 05:40:39,514 INFO L158 Benchmark]: CDTParser took 0.23ms. Allocated memory is still 201.3MB. Free memory is still 123.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 05:40:39,514 INFO L158 Benchmark]: CACSL2BoogieTranslator took 256.91ms. Allocated memory is still 142.6MB. Free memory was 112.7MB in the beginning and 100.9MB in the end (delta: 11.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 05:40:39,515 INFO L158 Benchmark]: Boogie Procedure Inliner took 33.09ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 99.4MB in the end (delta: 978.7kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 05:40:39,515 INFO L158 Benchmark]: Boogie Preprocessor took 43.63ms. Allocated memory is still 142.6MB. Free memory was 99.4MB in the beginning and 97.9MB in the end (delta: 1.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 05:40:39,516 INFO L158 Benchmark]: RCFGBuilder took 305.75ms. Allocated memory is still 142.6MB. Free memory was 97.4MB in the beginning and 84.1MB in the end (delta: 13.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 05:40:39,516 INFO L158 Benchmark]: TraceAbstraction took 6214.18ms. Allocated memory is still 142.6MB. Free memory was 83.6MB in the beginning and 88.2MB in the end (delta: -4.6MB). Peak memory consumption was 1.4MB. Max. memory is 16.1GB. [2025-01-09 05:40:39,516 INFO L158 Benchmark]: Witness Printer took 4.05ms. Allocated memory is still 142.6MB. Free memory was 88.2MB in the beginning and 88.2MB in the end (delta: 27.1kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 05:40:39,517 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.23ms. Allocated memory is still 201.3MB. Free memory is still 123.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 256.91ms. Allocated memory is still 142.6MB. Free memory was 112.7MB in the beginning and 100.9MB in the end (delta: 11.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 33.09ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 99.4MB in the end (delta: 978.7kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 43.63ms. Allocated memory is still 142.6MB. Free memory was 99.4MB in the beginning and 97.9MB in the end (delta: 1.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 305.75ms. Allocated memory is still 142.6MB. Free memory was 97.4MB in the beginning and 84.1MB in the end (delta: 13.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 6214.18ms. Allocated memory is still 142.6MB. Free memory was 83.6MB in the beginning and 88.2MB in the end (delta: -4.6MB). Peak memory consumption was 1.4MB. Max. memory is 16.1GB. * Witness Printer took 4.05ms. Allocated memory is still 142.6MB. Free memory was 88.2MB in the beginning and 88.2MB in the end (delta: 27.1kB). 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 104, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 100, overapproximation of someBinaryArithmeticFLOAToperation at line 92, 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 > -2.0f && IN < 2.0f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -2.0f && IN < 2.0f) [L100] CALL, EXPR f(IN) VAL [\old(x)=112] [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)=112] [L100] RET, EXPR f(IN) VAL [IN=112] [L100] CALL, EXPR fp(IN) VAL [\old(x)=112] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=112] [L100] RET, EXPR fp(IN) VAL [IN=112] [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=112, 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=112, x=110] [L102] x = x - f(x)/fp(x) [L104] CALL, EXPR f(x) 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] [L104] RET, EXPR f(x) VAL [IN=112, x=111] [L104] CALL, EXPR fp(x) 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] [L104] RET, EXPR fp(x) VAL [IN=112, x=111] [L104] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=112] [L109] reach_error() VAL [IN=112] - 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, 45 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 6.1s, OverallIterations: 10, TraceHistogramMax: 7, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 1.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 44 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 40 mSDsluCounter, 2477 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2131 mSDsCounter, 37 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 856 IncrementalHoareTripleChecker+Invalid, 893 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 37 mSolverCounterUnsat, 346 mSDtfsCounter, 856 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 308 GetRequests, 197 SyntacticMatches, 2 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 396 ImplicationChecksByTransitivity, 1.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=66occurred in iteration=6, InterpolantAutomatonStates: 68, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 7 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 3.0s InterpolantComputationTime, 341 NumberOfCodeBlocks, 337 NumberOfCodeBlocksAsserted, 42 NumberOfCheckSat, 374 ConstructedInterpolants, 0 QuantifiedInterpolants, 1958 SizeOfPredicates, 18 NumberOfNonLiveVariables, 549 ConjunctsInSsa, 96 ConjunctsInUnsatCore, 19 InterpolantComputations, 3 PerfectInterpolantSequences, 106/420 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-01-09 05:40:39,538 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, 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_3_8.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 5e702e85c3d7f91108386d3bed8993d879aa98d42d10adbcd14f5fa9bf29e29b --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 05:40:41,847 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 05:40:41,959 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2025-01-09 05:40:41,969 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 05:40:41,970 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 05:40:41,999 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 05:40:41,999 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 05:40:41,999 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 05:40:42,000 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 05:40:42,000 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 05:40:42,000 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 05:40:42,000 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 05:40:42,000 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 05:40:42,000 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 05:40:42,001 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 05:40:42,002 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 05:40:42,002 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 05:40:42,002 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-01-09 05:40:42,003 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 05:40:42,004 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 05:40:42,004 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:42,005 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:42,005 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 05:40:42,005 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 05:40:42,006 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 05:40:42,006 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 -> 5e702e85c3d7f91108386d3bed8993d879aa98d42d10adbcd14f5fa9bf29e29b [2025-01-09 05:40:42,336 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 05:40:42,345 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 05:40:42,347 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 05:40:42,350 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 05:40:42,350 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 05:40:42,352 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/combinations/gcd_4+newton_3_8.i [2025-01-09 05:40:43,679 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c29a248ec/dab5bfd58adc48c8a02e4219f6f08cd3/FLAG87a701692 [2025-01-09 05:40:43,896 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 05:40:43,897 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/combinations/gcd_4+newton_3_8.i [2025-01-09 05:40:43,905 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c29a248ec/dab5bfd58adc48c8a02e4219f6f08cd3/FLAG87a701692 [2025-01-09 05:40:43,924 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c29a248ec/dab5bfd58adc48c8a02e4219f6f08cd3 [2025-01-09 05:40:43,926 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 05:40:43,929 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 05:40:43,931 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 05:40:43,931 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 05:40:43,935 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 05:40:43,936 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:40:43" (1/1) ... [2025-01-09 05:40:43,936 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@69a9ceb0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:43, skipping insertion in model container [2025-01-09 05:40:43,937 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 05:40:43" (1/1) ... [2025-01-09 05:40:43,952 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 05:40:44,091 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_3_8.i[1224,1237] [2025-01-09 05:40:44,130 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_3_8.i[2848,2861] [2025-01-09 05:40:44,132 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 05:40:44,151 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 05:40:44,165 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_3_8.i[1224,1237] [2025-01-09 05:40:44,183 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_3_8.i[2848,2861] [2025-01-09 05:40:44,187 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 05:40:44,207 INFO L204 MainTranslator]: Completed translation [2025-01-09 05:40:44,207 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44 WrapperNode [2025-01-09 05:40:44,207 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 05:40:44,208 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 05:40:44,210 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 05:40:44,210 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 05:40:44,215 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,227 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,247 INFO L138 Inliner]: procedures = 28, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 78 [2025-01-09 05:40:44,249 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 05:40:44,250 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 05:40:44,250 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 05:40:44,250 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 05:40:44,257 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,259 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,266 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,278 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-01-09 05:40:44,278 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,278 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,284 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,285 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,288 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,291 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,292 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,299 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 05:40:44,300 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 05:40:44,300 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 05:40:44,300 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 05:40:44,301 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (1/1) ... [2025-01-09 05:40:44,314 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 05:40:44,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:44,339 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-01-09 05:40:44,342 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-01-09 05:40:44,366 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 05:40:44,367 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-01-09 05:40:44,367 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-01-09 05:40:44,367 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2025-01-09 05:40:44,367 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2025-01-09 05:40:44,367 INFO L130 BoogieDeclarations]: Found specification of procedure f [2025-01-09 05:40:44,367 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2025-01-09 05:40:44,367 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 05:40:44,368 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 05:40:44,368 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 05:40:44,368 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 05:40:44,444 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 05:40:44,446 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 05:40:58,706 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2025-01-09 05:40:58,706 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 05:40:58,715 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 05:40:58,716 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-09 05:40:58,716 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:40:58 BoogieIcfgContainer [2025-01-09 05:40:58,716 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 05:40:58,719 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 05:40:58,720 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 05:40:58,724 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 05:40:58,725 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 05:40:43" (1/3) ... [2025-01-09 05:40:58,726 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77b2450b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:40:58, skipping insertion in model container [2025-01-09 05:40:58,726 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 05:40:44" (2/3) ... [2025-01-09 05:40:58,726 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77b2450b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 05:40:58, skipping insertion in model container [2025-01-09 05:40:58,727 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 05:40:58" (3/3) ... [2025-01-09 05:40:58,728 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_8.i [2025-01-09 05:40:58,739 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 05:40:58,740 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_8.i that has 4 procedures, 45 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2025-01-09 05:40:58,781 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 05:40:58,790 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;@14a321ee, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 05:40:58,790 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2025-01-09 05:40:58,794 INFO L276 IsEmpty]: Start isEmpty. Operand has 45 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 32 states have internal predecessors, (41), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-01-09 05:40:58,797 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2025-01-09 05:40:58,797 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:58,798 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:58,798 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:58,801 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:58,801 INFO L85 PathProgramCache]: Analyzing trace with hash -1787067343, now seen corresponding path program 1 times [2025-01-09 05:40:58,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:40:58,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1970468403] [2025-01-09 05:40:58,807 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:58,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:58,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:58,809 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:58,811 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 05:40:58,863 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 11 statements into 1 equivalence classes. [2025-01-09 05:40:58,886 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 11 of 11 statements. [2025-01-09 05:40:58,887 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:58,887 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:58,890 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-09 05:40:58,893 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:59,002 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:59,003 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 05:40:59,003 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:40:59,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1970468403] [2025-01-09 05:40:59,004 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1970468403] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 05:40:59,004 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 05:40:59,004 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-09 05:40:59,005 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [870678425] [2025-01-09 05:40:59,006 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 05:40:59,011 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-09 05:40:59,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:40:59,028 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-09 05:40:59,029 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-09 05:40:59,031 INFO L87 Difference]: Start difference. First operand has 45 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 32 states have internal predecessors, (41), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) 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-01-09 05:40:59,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:59,180 INFO L93 Difference]: Finished difference Result 87 states and 117 transitions. [2025-01-09 05:40:59,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-09 05:40:59,183 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-01-09 05:40:59,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:59,188 INFO L225 Difference]: With dead ends: 87 [2025-01-09 05:40:59,189 INFO L226 Difference]: Without dead ends: 40 [2025-01-09 05:40:59,191 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-01-09 05:40:59,194 INFO L435 NwaCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 94 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-01-09 05:40:59,195 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 94 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 05:40:59,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-01-09 05:40:59,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 38. [2025-01-09 05:40:59,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:59,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2025-01-09 05:40:59,233 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 11 [2025-01-09 05:40:59,234 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:59,234 INFO L471 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2025-01-09 05:40:59,234 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-01-09 05:40:59,235 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2025-01-09 05:40:59,237 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-01-09 05:40:59,237 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:59,237 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:59,249 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-01-09 05:40:59,438 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-01-09 05:40:59,438 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:59,439 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:59,439 INFO L85 PathProgramCache]: Analyzing trace with hash -1509370903, now seen corresponding path program 1 times [2025-01-09 05:40:59,440 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:40:59,440 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1476963153] [2025-01-09 05:40:59,440 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:59,440 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:59,440 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:40:59,443 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:40:59,444 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 05:40:59,479 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-01-09 05:40:59,501 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-01-09 05:40:59,501 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:40:59,501 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:40:59,505 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-09 05:40:59,507 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:40:59,604 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:40:59,604 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 05:40:59,604 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:40:59,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1476963153] [2025-01-09 05:40:59,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1476963153] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 05:40:59,604 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 05:40:59,608 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-09 05:40:59,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1382925190] [2025-01-09 05:40:59,609 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 05:40:59,610 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-09 05:40:59,610 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:40:59,610 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-09 05:40:59,610 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-09 05:40:59,611 INFO L87 Difference]: Start difference. First operand 38 states and 46 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-01-09 05:40:59,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:40:59,774 INFO L93 Difference]: Finished difference Result 53 states and 66 transitions. [2025-01-09 05:40:59,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-09 05:40:59,775 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-01-09 05:40:59,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:40:59,777 INFO L225 Difference]: With dead ends: 53 [2025-01-09 05:40:59,777 INFO L226 Difference]: Without dead ends: 40 [2025-01-09 05:40:59,777 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-01-09 05:40:59,778 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 4 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 77 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-01-09 05:40:59,778 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 77 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 05:40:59,780 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2025-01-09 05:40:59,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2025-01-09 05:40:59,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 26 states have (on average 1.1923076923076923) internal successors, (31), 28 states have internal predecessors, (31), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:40:59,791 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2025-01-09 05:40:59,792 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 12 [2025-01-09 05:40:59,792 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:40:59,793 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2025-01-09 05:40:59,793 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-01-09 05:40:59,793 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2025-01-09 05:40:59,795 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-01-09 05:40:59,795 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:40:59,795 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:40:59,804 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-01-09 05:40:59,995 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-01-09 05:40:59,996 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:40:59,997 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:40:59,997 INFO L85 PathProgramCache]: Analyzing trace with hash -1983253012, now seen corresponding path program 1 times [2025-01-09 05:40:59,997 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:40:59,997 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1178812190] [2025-01-09 05:40:59,998 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:40:59,998 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:40:59,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:41:00,000 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:41:00,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 05:41:00,055 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-01-09 05:41:00,083 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-01-09 05:41:00,084 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:41:00,084 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:41:00,087 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-01-09 05:41:00,090 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:41:00,552 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:00,553 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:41:00,878 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:00,878 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:41:00,878 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1178812190] [2025-01-09 05:41:00,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1178812190] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:41:00,879 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:41:00,879 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2025-01-09 05:41:00,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [6847613] [2025-01-09 05:41:00,879 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:41:00,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-01-09 05:41:00,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:41:00,880 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-01-09 05:41:00,880 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2025-01-09 05:41:00,880 INFO L87 Difference]: Start difference. First operand 40 states and 48 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-01-09 05:41:01,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:41:01,313 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2025-01-09 05:41:01,314 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 05:41:01,314 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-01-09 05:41:01,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:41:01,315 INFO L225 Difference]: With dead ends: 57 [2025-01-09 05:41:01,315 INFO L226 Difference]: Without dead ends: 45 [2025-01-09 05:41:01,315 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2025-01-09 05:41:01,316 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 5 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2025-01-09 05:41:01,316 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 147 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2025-01-09 05:41:01,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-01-09 05:41:01,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 43. [2025-01-09 05:41:01,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:41:01,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 51 transitions. [2025-01-09 05:41:01,327 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 51 transitions. Word has length 14 [2025-01-09 05:41:01,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:41:01,328 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 51 transitions. [2025-01-09 05:41:01,328 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-01-09 05:41:01,328 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 51 transitions. [2025-01-09 05:41:01,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2025-01-09 05:41:01,328 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:41:01,330 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:41:01,342 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-01-09 05:41:01,531 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-01-09 05:41:01,531 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:41:01,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:41:01,532 INFO L85 PathProgramCache]: Analyzing trace with hash 1519745332, now seen corresponding path program 1 times [2025-01-09 05:41:01,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:41:01,533 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [834560898] [2025-01-09 05:41:01,533 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:41:01,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:41:01,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:41:01,535 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:41:01,537 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 05:41:01,564 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-01-09 05:41:01,583 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-01-09 05:41:01,583 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:41:01,584 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:41:01,587 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-01-09 05:41:01,590 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:41:02,101 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 05:41:02,101 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:41:02,893 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 05:41:02,893 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:41:02,894 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [834560898] [2025-01-09 05:41:02,894 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [834560898] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:41:02,894 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:41:02,894 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 6] total 8 [2025-01-09 05:41:02,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [454593536] [2025-01-09 05:41:02,894 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:41:02,895 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2025-01-09 05:41:02,895 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:41:02,895 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-01-09 05:41:02,895 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2025-01-09 05:41:02,895 INFO L87 Difference]: Start difference. First operand 43 states and 51 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 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-01-09 05:41:03,314 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:41:03,317 INFO L93 Difference]: Finished difference Result 58 states and 70 transitions. [2025-01-09 05:41:03,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 05:41:03,318 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 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-01-09 05:41:03,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:41:03,319 INFO L225 Difference]: With dead ends: 58 [2025-01-09 05:41:03,319 INFO L226 Difference]: Without dead ends: 45 [2025-01-09 05:41:03,319 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2025-01-09 05:41:03,320 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 148 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-01-09 05:41:03,320 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 148 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-01-09 05:41:03,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2025-01-09 05:41:03,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2025-01-09 05:41:03,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 33 states have internal predecessors, (35), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:41:03,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2025-01-09 05:41:03,329 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 52 transitions. Word has length 18 [2025-01-09 05:41:03,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:41:03,329 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 52 transitions. [2025-01-09 05:41:03,329 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 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-01-09 05:41:03,329 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 52 transitions. [2025-01-09 05:41:03,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-01-09 05:41:03,330 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:41:03,330 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:41:03,338 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-01-09 05:41:03,530 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-01-09 05:41:03,531 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:41:03,531 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:41:03,531 INFO L85 PathProgramCache]: Analyzing trace with hash 316493493, now seen corresponding path program 2 times [2025-01-09 05:41:03,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:41:03,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1576829147] [2025-01-09 05:41:03,532 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 05:41:03,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:41:03,532 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:41:03,535 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:41:03,536 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-01-09 05:41:03,563 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 20 statements into 2 equivalence classes. [2025-01-09 05:41:03,588 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 20 of 20 statements. [2025-01-09 05:41:03,588 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 05:41:03,588 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:41:03,592 INFO L256 TraceCheckSpWp]: Trace formula consists of 53 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-01-09 05:41:03,594 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:41:04,750 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:04,751 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:41:05,928 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:05,932 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:41:05,933 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1576829147] [2025-01-09 05:41:05,933 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1576829147] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:41:05,933 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:41:05,933 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2025-01-09 05:41:05,933 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1240374907] [2025-01-09 05:41:05,933 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:41:05,934 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2025-01-09 05:41:05,934 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:41:05,934 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2025-01-09 05:41:05,934 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2025-01-09 05:41:05,935 INFO L87 Difference]: Start difference. First operand 45 states and 52 transitions. Second operand has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 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-01-09 05:41:08,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:41:08,751 INFO L93 Difference]: Finished difference Result 78 states and 101 transitions. [2025-01-09 05:41:08,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2025-01-09 05:41:08,752 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 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-01-09 05:41:08,752 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:41:08,753 INFO L225 Difference]: With dead ends: 78 [2025-01-09 05:41:08,753 INFO L226 Difference]: Without dead ends: 65 [2025-01-09 05:41:08,754 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=113, Invalid=267, Unknown=0, NotChecked=0, Total=380 [2025-01-09 05:41:08,755 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 15 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2025-01-09 05:41:08,755 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 218 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2025-01-09 05:41:08,755 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2025-01-09 05:41:08,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 64. [2025-01-09 05:41:08,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 50 states have (on average 1.26) internal successors, (63), 52 states have internal predecessors, (63), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-01-09 05:41:08,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2025-01-09 05:41:08,774 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 20 [2025-01-09 05:41:08,774 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:41:08,774 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2025-01-09 05:41:08,774 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 12 states have internal predecessors, (32), 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-01-09 05:41:08,774 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2025-01-09 05:41:08,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2025-01-09 05:41:08,775 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:41:08,775 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:41:08,787 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-01-09 05:41:08,975 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-01-09 05:41:08,976 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:41:08,976 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:41:08,977 INFO L85 PathProgramCache]: Analyzing trace with hash 718801786, now seen corresponding path program 3 times [2025-01-09 05:41:08,977 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:41:08,977 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1660599806] [2025-01-09 05:41:08,977 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-09 05:41:08,977 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:41:08,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:41:08,979 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:41:08,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2025-01-09 05:41:09,006 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 22 statements into 6 equivalence classes. [2025-01-09 05:41:09,062 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 22 of 22 statements. [2025-01-09 05:41:09,062 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-01-09 05:41:09,062 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:41:09,066 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-01-09 05:41:09,068 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:41:11,905 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:11,906 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 05:41:29,410 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 05:41:29,410 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-01-09 05:41:29,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1660599806] [2025-01-09 05:41:29,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1660599806] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 05:41:29,410 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 05:41:29,410 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 14] total 24 [2025-01-09 05:41:29,410 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1924565210] [2025-01-09 05:41:29,410 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 05:41:29,411 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2025-01-09 05:41:29,411 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-01-09 05:41:29,411 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2025-01-09 05:41:29,411 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=452, Unknown=0, NotChecked=0, Total=552 [2025-01-09 05:41:29,412 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 24 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 22 states have internal predecessors, (39), 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-01-09 05:41:34,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 05:41:34,176 INFO L93 Difference]: Finished difference Result 79 states and 97 transitions. [2025-01-09 05:41:34,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2025-01-09 05:41:34,177 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 22 states have internal predecessors, (39), 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-01-09 05:41:34,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 05:41:34,178 INFO L225 Difference]: With dead ends: 79 [2025-01-09 05:41:34,178 INFO L226 Difference]: Without dead ends: 48 [2025-01-09 05:41:34,179 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 15.6s TimeCoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2025-01-09 05:41:34,179 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 3 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 257 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 484 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 257 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2025-01-09 05:41:34,180 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 484 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 257 Invalid, 0 Unknown, 0 Unchecked, 4.2s Time] [2025-01-09 05:41:34,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2025-01-09 05:41:34,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2025-01-09 05:41:34,186 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 35 states have (on average 1.0285714285714285) internal successors, (36), 36 states have internal predecessors, (36), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2025-01-09 05:41:34,187 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 51 transitions. [2025-01-09 05:41:34,187 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 51 transitions. Word has length 22 [2025-01-09 05:41:34,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 05:41:34,187 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 51 transitions. [2025-01-09 05:41:34,187 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 22 states have internal predecessors, (39), 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-01-09 05:41:34,187 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 51 transitions. [2025-01-09 05:41:34,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2025-01-09 05:41:34,189 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 05:41:34,189 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 05:41:34,197 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2025-01-09 05:41:34,390 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:41:34,390 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 05:41:34,390 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 05:41:34,390 INFO L85 PathProgramCache]: Analyzing trace with hash -2015702026, now seen corresponding path program 1 times [2025-01-09 05:41:34,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-01-09 05:41:34,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [182933721] [2025-01-09 05:41:34,391 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 05:41:34,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 05:41:34,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 05:41:34,393 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 05:41:34,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-01-09 05:41:34,423 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 27 statements into 1 equivalence classes. [2025-01-09 05:41:34,453 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 27 of 27 statements. [2025-01-09 05:41:34,454 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 05:41:34,454 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 05:41:34,460 INFO L256 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 21 conjuncts are in the unsatisfiable core [2025-01-09 05:41:34,462 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 05:41:37,875 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 05:41:37,876 INFO L312 TraceCheckSpWp]: Computing backward predicates...