./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-crafted/xor5.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/array-crafted/xor5.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 a4ee2cdc1f0cbbd62309a70b71e98ce771ffa71f4ebd85e731799a93fbbc3919 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-08 22:25:19,745 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-08 22:25:19,795 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-08 22:25:19,799 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-08 22:25:19,799 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-08 22:25:19,822 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-08 22:25:19,823 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-08 22:25:19,823 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-08 22:25:19,823 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-08 22:25:19,823 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-08 22:25:19,824 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-08 22:25:19,824 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-08 22:25:19,824 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-08 22:25:19,824 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-08 22:25:19,824 INFO L153 SettingsManager]: * Use SBE=true [2025-01-08 22:25:19,824 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-08 22:25:19,824 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-08 22:25:19,824 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-08 22:25:19,825 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-08 22:25:19,825 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-08 22:25:19,825 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-08 22:25:19,825 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-08 22:25:19,826 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-08 22:25:19,826 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 -> a4ee2cdc1f0cbbd62309a70b71e98ce771ffa71f4ebd85e731799a93fbbc3919 [2025-01-08 22:25:20,041 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-08 22:25:20,049 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-08 22:25:20,052 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-08 22:25:20,053 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-08 22:25:20,053 INFO L274 PluginConnector]: CDTParser initialized [2025-01-08 22:25:20,054 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-crafted/xor5.i [2025-01-08 22:25:21,227 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c22a6e18d/fd64608c46a64676b9ac8aac645942fa/FLAGe58cbbabf [2025-01-08 22:25:21,439 INFO L384 CDTParser]: Found 1 translation units. [2025-01-08 22:25:21,439 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/array-crafted/xor5.i [2025-01-08 22:25:21,458 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c22a6e18d/fd64608c46a64676b9ac8aac645942fa/FLAGe58cbbabf [2025-01-08 22:25:21,480 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/c22a6e18d/fd64608c46a64676b9ac8aac645942fa [2025-01-08 22:25:21,482 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-08 22:25:21,484 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-08 22:25:21,485 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-08 22:25:21,485 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-08 22:25:21,488 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-08 22:25:21,489 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,490 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@74f7bfe2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21, skipping insertion in model container [2025-01-08 22:25:21,491 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,502 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-08 22:25:21,630 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/array-crafted/xor5.i[1364,1377] [2025-01-08 22:25:21,634 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-08 22:25:21,642 INFO L200 MainTranslator]: Completed pre-run [2025-01-08 22:25:21,657 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/array-crafted/xor5.i[1364,1377] [2025-01-08 22:25:21,657 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-08 22:25:21,668 INFO L204 MainTranslator]: Completed translation [2025-01-08 22:25:21,669 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21 WrapperNode [2025-01-08 22:25:21,669 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-08 22:25:21,670 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-08 22:25:21,670 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-08 22:25:21,670 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-08 22:25:21,674 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,683 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,693 INFO L138 Inliner]: procedures = 16, calls = 29, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 75 [2025-01-08 22:25:21,695 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-08 22:25:21,695 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-08 22:25:21,696 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-08 22:25:21,696 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-08 22:25:21,702 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,702 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,704 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,712 INFO L175 MemorySlicer]: Split 20 memory accesses to 3 slices as follows [2, 7, 11]. 55 percent of accesses are in the largest equivalence class. The 9 initializations are split as follows [2, 7, 0]. The 5 writes are split as follows [0, 0, 5]. [2025-01-08 22:25:21,712 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,712 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,716 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,716 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,718 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,719 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,720 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,721 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-08 22:25:21,721 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-08 22:25:21,722 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-08 22:25:21,722 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-08 22:25:21,722 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (1/1) ... [2025-01-08 22:25:21,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-08 22:25:21,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:25:21,745 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-08 22:25:21,747 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-08 22:25:21,764 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-08 22:25:21,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-08 22:25:21,764 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-08 22:25:21,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2025-01-08 22:25:21,765 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2025-01-08 22:25:21,766 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2025-01-08 22:25:21,766 INFO L130 BoogieDeclarations]: Found specification of procedure xor [2025-01-08 22:25:21,766 INFO L138 BoogieDeclarations]: Found implementation of procedure xor [2025-01-08 22:25:21,766 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-01-08 22:25:21,828 INFO L234 CfgBuilder]: Building ICFG [2025-01-08 22:25:21,829 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-08 22:25:21,932 INFO L? ?]: Removed 20 outVars from TransFormulas that were not future-live. [2025-01-08 22:25:21,933 INFO L283 CfgBuilder]: Performing block encoding [2025-01-08 22:25:21,938 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-08 22:25:21,938 INFO L312 CfgBuilder]: Removed 0 assume(true) statements. [2025-01-08 22:25:21,938 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.01 10:25:21 BoogieIcfgContainer [2025-01-08 22:25:21,939 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-08 22:25:21,940 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-08 22:25:21,940 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-08 22:25:21,943 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-08 22:25:21,943 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.01 10:25:21" (1/3) ... [2025-01-08 22:25:21,944 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54529639 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.01 10:25:21, skipping insertion in model container [2025-01-08 22:25:21,944 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.01 10:25:21" (2/3) ... [2025-01-08 22:25:21,944 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@54529639 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.01 10:25:21, skipping insertion in model container [2025-01-08 22:25:21,944 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.01 10:25:21" (3/3) ... [2025-01-08 22:25:21,945 INFO L128 eAbstractionObserver]: Analyzing ICFG xor5.i [2025-01-08 22:25:21,954 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-08 22:25:21,956 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG xor5.i that has 2 procedures, 28 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2025-01-08 22:25:21,993 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-08 22:25:22,002 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;@4d155ab5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-08 22:25:22,003 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-08 22:25:22,005 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 23 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-08 22:25:22,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2025-01-08 22:25:22,011 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:25:22,012 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:25:22,013 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:25:22,016 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:25:22,016 INFO L85 PathProgramCache]: Analyzing trace with hash -6422848, now seen corresponding path program 1 times [2025-01-08 22:25:22,022 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:25:22,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1914149914] [2025-01-08 22:25:22,024 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:22,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:25:22,090 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 25 statements into 1 equivalence classes. [2025-01-08 22:25:22,111 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 25 of 25 statements. [2025-01-08 22:25:22,111 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:22,112 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:22,281 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-08 22:25:22,282 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:25:22,282 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1914149914] [2025-01-08 22:25:22,282 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1914149914] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-08 22:25:22,286 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-08 22:25:22,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-01-08 22:25:22,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1968209508] [2025-01-08 22:25:22,288 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-08 22:25:22,291 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2025-01-08 22:25:22,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:25:22,305 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2025-01-08 22:25:22,306 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2025-01-08 22:25:22,307 INFO L87 Difference]: Start difference. First operand has 28 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 23 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 3 states have internal predecessors, (13), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-01-08 22:25:22,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:25:22,350 INFO L93 Difference]: Finished difference Result 53 states and 70 transitions. [2025-01-08 22:25:22,352 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2025-01-08 22:25:22,353 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, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2025-01-08 22:25:22,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:25:22,357 INFO L225 Difference]: With dead ends: 53 [2025-01-08 22:25:22,358 INFO L226 Difference]: Without dead ends: 24 [2025-01-08 22:25:22,361 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-08 22:25:22,363 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 25 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 60 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-08 22:25:22,363 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 60 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-08 22:25:22,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2025-01-08 22:25:22,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2025-01-08 22:25:22,386 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 19 states have internal predecessors, (25), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-08 22:25:22,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 31 transitions. [2025-01-08 22:25:22,392 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 31 transitions. Word has length 25 [2025-01-08 22:25:22,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:25:22,392 INFO L471 AbstractCegarLoop]: Abstraction has 24 states and 31 transitions. [2025-01-08 22:25:22,393 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, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2025-01-08 22:25:22,393 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 31 transitions. [2025-01-08 22:25:22,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2025-01-08 22:25:22,395 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:25:22,395 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:25:22,395 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-08 22:25:22,396 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:25:22,396 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:25:22,397 INFO L85 PathProgramCache]: Analyzing trace with hash 1547790341, now seen corresponding path program 1 times [2025-01-08 22:25:22,397 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:25:22,397 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1508947951] [2025-01-08 22:25:22,397 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:22,397 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:25:22,408 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-01-08 22:25:22,417 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-01-08 22:25:22,418 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:22,418 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:22,531 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-08 22:25:22,532 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:25:22,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1508947951] [2025-01-08 22:25:22,532 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1508947951] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:25:22,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1873275325] [2025-01-08 22:25:22,532 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:22,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:25:22,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:25:22,535 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-08 22:25:22,536 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-08 22:25:22,575 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 26 statements into 1 equivalence classes. [2025-01-08 22:25:22,616 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 26 of 26 statements. [2025-01-08 22:25:22,616 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:22,616 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:22,619 INFO L256 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-01-08 22:25:22,623 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-08 22:25:22,671 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-08 22:25:22,672 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-08 22:25:22,720 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2025-01-08 22:25:22,721 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1873275325] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-08 22:25:22,722 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-08 22:25:22,722 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 9 [2025-01-08 22:25:22,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [238988540] [2025-01-08 22:25:22,722 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-08 22:25:22,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2025-01-08 22:25:22,724 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:25:22,724 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-01-08 22:25:22,725 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2025-01-08 22:25:22,725 INFO L87 Difference]: Start difference. First operand 24 states and 31 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 1 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-08 22:25:22,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:25:22,799 INFO L93 Difference]: Finished difference Result 50 states and 71 transitions. [2025-01-08 22:25:22,800 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2025-01-08 22:25:22,800 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 1 states have call predecessors, (7), 2 states have call successors, (7) Word has length 26 [2025-01-08 22:25:22,800 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:25:22,800 INFO L225 Difference]: With dead ends: 50 [2025-01-08 22:25:22,801 INFO L226 Difference]: Without dead ends: 31 [2025-01-08 22:25:22,801 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2025-01-08 22:25:22,802 INFO L435 NwaCegarLoop]: 23 mSDtfsCounter, 42 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 60 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 60 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-08 22:25:22,802 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 87 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 60 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-08 22:25:22,803 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2025-01-08 22:25:22,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 26. [2025-01-08 22:25:22,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 21 states have internal predecessors, (27), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-08 22:25:22,808 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 33 transitions. [2025-01-08 22:25:22,809 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 33 transitions. Word has length 26 [2025-01-08 22:25:22,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:25:22,809 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 33 transitions. [2025-01-08 22:25:22,809 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 9 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 1 states have call predecessors, (7), 2 states have call successors, (7) [2025-01-08 22:25:22,809 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 33 transitions. [2025-01-08 22:25:22,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2025-01-08 22:25:22,810 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:25:22,810 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:25:22,816 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-08 22:25:23,014 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:25:23,014 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:25:23,015 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:25:23,015 INFO L85 PathProgramCache]: Analyzing trace with hash 1510909249, now seen corresponding path program 1 times [2025-01-08 22:25:23,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:25:23,015 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2015179638] [2025-01-08 22:25:23,015 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:23,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:25:23,027 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 36 statements into 1 equivalence classes. [2025-01-08 22:25:23,046 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 36 of 36 statements. [2025-01-08 22:25:23,046 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:23,047 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:23,143 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2025-01-08 22:25:23,143 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:25:23,143 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2015179638] [2025-01-08 22:25:23,143 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2015179638] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-08 22:25:23,144 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-08 22:25:23,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-01-08 22:25:23,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [223458182] [2025-01-08 22:25:23,144 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-08 22:25:23,144 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-01-08 22:25:23,144 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:25:23,144 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-01-08 22:25:23,144 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2025-01-08 22:25:23,144 INFO L87 Difference]: Start difference. First operand 26 states and 33 transitions. Second operand has 4 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-08 22:25:23,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:25:23,169 INFO L93 Difference]: Finished difference Result 42 states and 53 transitions. [2025-01-08 22:25:23,170 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-01-08 22:25:23,170 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 36 [2025-01-08 22:25:23,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:25:23,171 INFO L225 Difference]: With dead ends: 42 [2025-01-08 22:25:23,171 INFO L226 Difference]: Without dead ends: 27 [2025-01-08 22:25:23,172 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2025-01-08 22:25:23,172 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 22 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-08 22:25:23,172 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 38 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-08 22:25:23,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-01-08 22:25:23,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-01-08 22:25:23,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 22 states have internal predecessors, (28), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-08 22:25:23,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2025-01-08 22:25:23,178 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 36 [2025-01-08 22:25:23,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:25:23,179 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2025-01-08 22:25:23,179 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2025-01-08 22:25:23,179 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2025-01-08 22:25:23,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2025-01-08 22:25:23,180 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:25:23,180 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:25:23,180 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2025-01-08 22:25:23,181 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:25:23,181 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:25:23,181 INFO L85 PathProgramCache]: Analyzing trace with hash -190351074, now seen corresponding path program 1 times [2025-01-08 22:25:23,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:25:23,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [912251842] [2025-01-08 22:25:23,181 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:23,182 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:25:23,191 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-08 22:25:23,259 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-08 22:25:23,259 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:23,259 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:25,103 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 9 proven. 19 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-01-08 22:25:25,104 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:25:25,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [912251842] [2025-01-08 22:25:25,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [912251842] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:25:25,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2008873610] [2025-01-08 22:25:25,104 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:25,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:25:25,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:25:25,107 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-08 22:25:25,108 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-08 22:25:25,144 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 37 statements into 1 equivalence classes. [2025-01-08 22:25:25,166 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 37 of 37 statements. [2025-01-08 22:25:25,166 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:25,166 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:25,168 WARN L254 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 102 conjuncts are in the unsatisfiable core [2025-01-08 22:25:25,172 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-08 22:25:25,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-08 22:25:25,594 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 64 treesize of output 33 [2025-01-08 22:25:26,202 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-01-08 22:25:26,202 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 64 treesize of output 43 [2025-01-08 22:25:26,315 INFO L349 Elim1Store]: treesize reduction 24, result has 48.9 percent of original size [2025-01-08 22:25:26,316 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 68 treesize of output 62 [2025-01-08 22:25:27,350 INFO L349 Elim1Store]: treesize reduction 247, result has 19.0 percent of original size [2025-01-08 22:25:27,351 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 9 select indices, 9 select index equivalence classes, 1 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 176 treesize of output 157 [2025-01-08 22:25:27,443 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 15 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-08 22:25:27,444 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-08 22:25:27,683 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2008873610] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:25:27,683 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-08 22:25:27,683 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 31] total 55 [2025-01-08 22:25:27,683 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890463678] [2025-01-08 22:25:27,683 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-08 22:25:27,684 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 55 states [2025-01-08 22:25:27,684 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:25:27,684 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2025-01-08 22:25:27,685 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=198, Invalid=2882, Unknown=0, NotChecked=0, Total=3080 [2025-01-08 22:25:27,688 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 55 states, 50 states have (on average 1.16) internal successors, (58), 47 states have internal predecessors, (58), 6 states have call successors, (6), 3 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-01-08 22:25:30,270 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:25:30,271 INFO L93 Difference]: Finished difference Result 149 states and 214 transitions. [2025-01-08 22:25:30,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2025-01-08 22:25:30,271 INFO L78 Accepts]: Start accepts. Automaton has has 55 states, 50 states have (on average 1.16) internal successors, (58), 47 states have internal predecessors, (58), 6 states have call successors, (6), 3 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 37 [2025-01-08 22:25:30,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:25:30,273 INFO L225 Difference]: With dead ends: 149 [2025-01-08 22:25:30,274 INFO L226 Difference]: Without dead ends: 141 [2025-01-08 22:25:30,276 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2342 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=560, Invalid=7450, Unknown=0, NotChecked=0, Total=8010 [2025-01-08 22:25:30,277 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 211 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 2396 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 216 SdHoareTripleChecker+Valid, 250 SdHoareTripleChecker+Invalid, 2457 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 2396 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2025-01-08 22:25:30,277 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [216 Valid, 250 Invalid, 2457 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 2396 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2025-01-08 22:25:30,277 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2025-01-08 22:25:30,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 84. [2025-01-08 22:25:30,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 68 states have (on average 1.3970588235294117) internal successors, (95), 71 states have internal predecessors, (95), 10 states have call successors, (10), 3 states have call predecessors, (10), 5 states have return successors, (18), 9 states have call predecessors, (18), 10 states have call successors, (18) [2025-01-08 22:25:30,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 123 transitions. [2025-01-08 22:25:30,289 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 123 transitions. Word has length 37 [2025-01-08 22:25:30,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:25:30,289 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 123 transitions. [2025-01-08 22:25:30,290 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 55 states, 50 states have (on average 1.16) internal successors, (58), 47 states have internal predecessors, (58), 6 states have call successors, (6), 3 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-01-08 22:25:30,290 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 123 transitions. [2025-01-08 22:25:30,291 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-08 22:25:30,291 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:25:30,291 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:25:30,298 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-08 22:25:30,491 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:25:30,492 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:25:30,492 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:25:30,492 INFO L85 PathProgramCache]: Analyzing trace with hash 528893712, now seen corresponding path program 1 times [2025-01-08 22:25:30,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:25:30,492 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1896707351] [2025-01-08 22:25:30,492 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:30,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:25:30,500 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-08 22:25:30,513 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:25:30,514 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:30,514 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:30,817 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-01-08 22:25:30,818 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:25:30,818 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1896707351] [2025-01-08 22:25:30,818 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1896707351] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:25:30,818 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [999562503] [2025-01-08 22:25:30,818 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-08 22:25:30,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:25:30,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:25:30,820 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-08 22:25:30,824 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-08 22:25:30,856 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 38 statements into 1 equivalence classes. [2025-01-08 22:25:30,874 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:25:30,874 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-08 22:25:30,874 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:25:30,875 INFO L256 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 43 conjuncts are in the unsatisfiable core [2025-01-08 22:25:30,878 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-08 22:25:30,905 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 12 [2025-01-08 22:25:30,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 19 [2025-01-08 22:25:30,999 INFO L349 Elim1Store]: treesize reduction 40, result has 36.5 percent of original size [2025-01-08 22:25:31,000 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 43 treesize of output 30 [2025-01-08 22:25:31,219 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 4 proven. 26 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-08 22:25:31,219 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-08 22:25:39,464 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 10 proven. 17 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2025-01-08 22:25:39,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [999562503] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-08 22:25:39,464 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-08 22:25:39,465 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15, 12] total 31 [2025-01-08 22:25:39,465 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [113231668] [2025-01-08 22:25:39,465 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-08 22:25:39,465 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-01-08 22:25:39,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:25:39,466 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-01-08 22:25:39,466 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=796, Unknown=2, NotChecked=0, Total=930 [2025-01-08 22:25:39,466 INFO L87 Difference]: Start difference. First operand 84 states and 123 transitions. Second operand has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 28 states have internal predecessors, (66), 9 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2025-01-08 22:25:43,478 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:25:47,483 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:25:51,491 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:25:55,683 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:25:59,690 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:03,705 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:11,958 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:24,724 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:26,235 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:30,241 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:34,248 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:39,574 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:43,582 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:48,733 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:52,739 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-01-08 22:26:52,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:26:52,908 INFO L93 Difference]: Finished difference Result 269 states and 396 transitions. [2025-01-08 22:26:52,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-01-08 22:26:52,909 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 28 states have internal predecessors, (66), 9 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) Word has length 38 [2025-01-08 22:26:52,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:26:52,911 INFO L225 Difference]: With dead ends: 269 [2025-01-08 22:26:52,911 INFO L226 Difference]: Without dead ends: 239 [2025-01-08 22:26:52,912 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 686 ImplicationChecksByTransitivity, 20.7s TimeCoverageRelationStatistics Valid=359, Invalid=2186, Unknown=5, NotChecked=0, Total=2550 [2025-01-08 22:26:52,912 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 149 mSDsluCounter, 377 mSDsCounter, 0 mSdLazyCounter, 657 mSolverCounterSat, 41 mSolverCounterUnsat, 21 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 61.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 155 SdHoareTripleChecker+Valid, 422 SdHoareTripleChecker+Invalid, 719 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 657 IncrementalHoareTripleChecker+Invalid, 21 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 61.1s IncrementalHoareTripleChecker+Time [2025-01-08 22:26:52,912 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [155 Valid, 422 Invalid, 719 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 657 Invalid, 21 Unknown, 0 Unchecked, 61.1s Time] [2025-01-08 22:26:52,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2025-01-08 22:26:52,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 154. [2025-01-08 22:26:52,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 128 states have (on average 1.4140625) internal successors, (181), 132 states have internal predecessors, (181), 15 states have call successors, (15), 8 states have call predecessors, (15), 10 states have return successors, (32), 13 states have call predecessors, (32), 15 states have call successors, (32) [2025-01-08 22:26:52,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 228 transitions. [2025-01-08 22:26:52,934 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 228 transitions. Word has length 38 [2025-01-08 22:26:52,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:26:52,935 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 228 transitions. [2025-01-08 22:26:52,935 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 28 states have internal predecessors, (66), 9 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2025-01-08 22:26:52,935 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 228 transitions. [2025-01-08 22:26:52,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-08 22:26:52,938 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:26:52,938 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:26:52,946 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2025-01-08 22:26:53,138 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:26:53,139 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:26:53,139 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:26:53,139 INFO L85 PathProgramCache]: Analyzing trace with hash -2139019884, now seen corresponding path program 2 times [2025-01-08 22:26:53,139 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:26:53,139 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [735967485] [2025-01-08 22:26:53,139 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-08 22:26:53,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:26:53,145 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-01-08 22:26:53,199 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:26:53,199 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-08 22:26:53,200 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:26:54,768 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2025-01-08 22:26:54,768 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:26:54,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [735967485] [2025-01-08 22:26:54,769 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [735967485] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:26:54,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [668214146] [2025-01-08 22:26:54,769 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-08 22:26:54,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:26:54,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:26:54,771 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-08 22:26:54,772 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-08 22:26:54,811 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-01-08 22:26:54,832 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:26:54,832 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-08 22:26:54,833 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:26:54,839 INFO L256 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 82 conjuncts are in the unsatisfiable core [2025-01-08 22:26:54,842 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-08 22:26:54,873 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-08 22:26:55,113 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 34 [2025-01-08 22:26:55,356 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 100 treesize of output 72 [2025-01-08 22:26:55,424 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2025-01-08 22:26:55,691 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 134 treesize of output 94 [2025-01-08 22:26:55,929 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 31 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-01-08 22:26:55,929 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-08 22:26:56,255 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 41 [2025-01-08 22:26:56,264 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 56 treesize of output 48 [2025-01-08 22:26:56,277 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 39 [2025-01-08 22:26:56,281 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 44 [2025-01-08 22:26:57,107 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 6 proven. 23 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2025-01-08 22:26:57,108 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [668214146] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-08 22:26:57,108 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-01-08 22:26:57,108 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 27, 26] total 61 [2025-01-08 22:26:57,108 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [38459071] [2025-01-08 22:26:57,108 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-01-08 22:26:57,109 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 61 states [2025-01-08 22:26:57,109 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:26:57,109 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2025-01-08 22:26:57,110 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=278, Invalid=3382, Unknown=0, NotChecked=0, Total=3660 [2025-01-08 22:26:57,110 INFO L87 Difference]: Start difference. First operand 154 states and 228 transitions. Second operand has 61 states, 55 states have (on average 1.4181818181818182) internal successors, (78), 55 states have internal predecessors, (78), 7 states have call successors, (9), 2 states have call predecessors, (9), 7 states have return successors, (9), 6 states have call predecessors, (9), 7 states have call successors, (9) [2025-01-08 22:26:58,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:26:58,731 INFO L93 Difference]: Finished difference Result 342 states and 522 transitions. [2025-01-08 22:26:58,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2025-01-08 22:26:58,732 INFO L78 Accepts]: Start accepts. Automaton has has 61 states, 55 states have (on average 1.4181818181818182) internal successors, (78), 55 states have internal predecessors, (78), 7 states have call successors, (9), 2 states have call predecessors, (9), 7 states have return successors, (9), 6 states have call predecessors, (9), 7 states have call successors, (9) Word has length 38 [2025-01-08 22:26:58,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:26:58,734 INFO L225 Difference]: With dead ends: 342 [2025-01-08 22:26:58,734 INFO L226 Difference]: Without dead ends: 338 [2025-01-08 22:26:58,736 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 38 SyntacticMatches, 6 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1653 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=448, Invalid=4954, Unknown=0, NotChecked=0, Total=5402 [2025-01-08 22:26:58,736 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 207 mSDsluCounter, 283 mSDsCounter, 0 mSdLazyCounter, 1776 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 219 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 1795 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 1776 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2025-01-08 22:26:58,736 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [219 Valid, 297 Invalid, 1795 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 1776 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2025-01-08 22:26:58,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 338 states. [2025-01-08 22:26:58,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 338 to 164. [2025-01-08 22:26:58,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 164 states, 136 states have (on average 1.4191176470588236) internal successors, (193), 141 states have internal predecessors, (193), 16 states have call successors, (16), 8 states have call predecessors, (16), 11 states have return successors, (40), 14 states have call predecessors, (40), 16 states have call successors, (40) [2025-01-08 22:26:58,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 249 transitions. [2025-01-08 22:26:58,760 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 249 transitions. Word has length 38 [2025-01-08 22:26:58,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:26:58,761 INFO L471 AbstractCegarLoop]: Abstraction has 164 states and 249 transitions. [2025-01-08 22:26:58,761 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 61 states, 55 states have (on average 1.4181818181818182) internal successors, (78), 55 states have internal predecessors, (78), 7 states have call successors, (9), 2 states have call predecessors, (9), 7 states have return successors, (9), 6 states have call predecessors, (9), 7 states have call successors, (9) [2025-01-08 22:26:58,761 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 249 transitions. [2025-01-08 22:26:58,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-08 22:26:58,762 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:26:58,762 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:26:58,768 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-08 22:26:58,963 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,SelfDestructingSolverStorable5 [2025-01-08 22:26:58,964 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:26:58,964 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:26:58,964 INFO L85 PathProgramCache]: Analyzing trace with hash 1313124944, now seen corresponding path program 3 times [2025-01-08 22:26:58,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:26:58,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1103689846] [2025-01-08 22:26:58,964 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-08 22:26:58,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:26:58,969 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 38 statements into 5 equivalence classes. [2025-01-08 22:26:58,980 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:26:58,980 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-01-08 22:26:58,981 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:26:59,308 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 8 proven. 20 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2025-01-08 22:26:59,308 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-08 22:26:59,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1103689846] [2025-01-08 22:26:59,308 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1103689846] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:26:59,308 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1936969354] [2025-01-08 22:26:59,308 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-01-08 22:26:59,308 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:26:59,309 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-08 22:26:59,311 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-08 22:26:59,312 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-08 22:26:59,352 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 38 statements into 5 equivalence classes. [2025-01-08 22:26:59,376 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) and asserted 38 of 38 statements. [2025-01-08 22:26:59,377 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2025-01-08 22:26:59,377 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-08 22:26:59,378 INFO L256 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 40 conjuncts are in the unsatisfiable core [2025-01-08 22:26:59,380 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-08 22:26:59,466 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 11 [2025-01-08 22:26:59,566 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2025-01-08 22:26:59,592 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-01-08 22:26:59,601 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2025-01-08 22:26:59,601 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 25 [2025-01-08 22:26:59,680 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 29 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-08 22:26:59,680 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-08 22:26:59,829 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1936969354] provided 0 perfect and 1 imperfect interpolant sequences [2025-01-08 22:26:59,830 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-08 22:26:59,830 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 15] total 26 [2025-01-08 22:26:59,830 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553255748] [2025-01-08 22:26:59,830 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-08 22:26:59,830 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2025-01-08 22:26:59,830 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-08 22:26:59,830 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2025-01-08 22:26:59,831 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=133, Invalid=797, Unknown=0, NotChecked=0, Total=930 [2025-01-08 22:26:59,831 INFO L87 Difference]: Start difference. First operand 164 states and 249 transitions. Second operand has 26 states, 25 states have (on average 2.24) internal successors, (56), 22 states have internal predecessors, (56), 5 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-01-08 22:27:00,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-08 22:27:00,425 INFO L93 Difference]: Finished difference Result 373 states and 551 transitions. [2025-01-08 22:27:00,425 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2025-01-08 22:27:00,425 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 25 states have (on average 2.24) internal successors, (56), 22 states have internal predecessors, (56), 5 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 38 [2025-01-08 22:27:00,426 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-08 22:27:00,427 INFO L225 Difference]: With dead ends: 373 [2025-01-08 22:27:00,427 INFO L226 Difference]: Without dead ends: 339 [2025-01-08 22:27:00,428 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 43 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 488 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=242, Invalid=1564, Unknown=0, NotChecked=0, Total=1806 [2025-01-08 22:27:00,428 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 105 mSDsluCounter, 426 mSDsCounter, 0 mSdLazyCounter, 700 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 111 SdHoareTripleChecker+Valid, 472 SdHoareTripleChecker+Invalid, 728 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 700 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-01-08 22:27:00,429 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [111 Valid, 472 Invalid, 728 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 700 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-01-08 22:27:00,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2025-01-08 22:27:00,469 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 255. [2025-01-08 22:27:00,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 255 states, 214 states have (on average 1.4532710280373833) internal successors, (311), 227 states have internal predecessors, (311), 20 states have call successors, (20), 13 states have call predecessors, (20), 20 states have return successors, (37), 14 states have call predecessors, (37), 20 states have call successors, (37) [2025-01-08 22:27:00,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 255 states to 255 states and 368 transitions. [2025-01-08 22:27:00,471 INFO L78 Accepts]: Start accepts. Automaton has 255 states and 368 transitions. Word has length 38 [2025-01-08 22:27:00,472 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-08 22:27:00,472 INFO L471 AbstractCegarLoop]: Abstraction has 255 states and 368 transitions. [2025-01-08 22:27:00,472 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 25 states have (on average 2.24) internal successors, (56), 22 states have internal predecessors, (56), 5 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-01-08 22:27:00,472 INFO L276 IsEmpty]: Start isEmpty. Operand 255 states and 368 transitions. [2025-01-08 22:27:00,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2025-01-08 22:27:00,474 INFO L210 NwaCegarLoop]: Found error trace [2025-01-08 22:27:00,474 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-08 22:27:00,479 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-08 22:27:00,674 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-08 22:27:00,675 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-08 22:27:00,675 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-08 22:27:00,675 INFO L85 PathProgramCache]: Analyzing trace with hash -583551889, now seen corresponding path program 4 times [2025-01-08 22:27:00,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-08 22:27:00,675 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1242063339] [2025-01-08 22:27:00,675 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2025-01-08 22:27:00,675 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-08 22:27:00,681 INFO L108 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST partitioned 39 statements into 2 equivalence classes. [2025-01-08 22:27:00,686 INFO L111 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) and asserted 39 of 39 statements. [2025-01-08 22:27:00,687 INFO L114 AnnotateAndAsserter]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 2 check-sat command(s) [2025-01-08 22:27:00,687 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat