./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4f9af400 extending candidate: java ['java'] extending candidate: /usr/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/oracle-jdk-bin-*/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/openjdk-*/bin/java ['java', '/usr/bin/java'] extending candidate: /usr/lib/jvm/java-*-openjdk-amd64/bin/java ['java', '/usr/bin/java', '/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java', '/usr/lib/jvm/java-17-openjdk-amd64/bin/java', '/usr/lib/jvm/java-11-openjdk-amd64/bin/java', '/usr/lib/jvm/java-1.17.0-openjdk-amd64/bin/java'] ['/root/.sdkman/candidates/java/21.0.5-tem/bin/java', '-Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config', '-Xmx15G', '-Xms4m', '-jar', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar', '-data', '@noDefault', '-ultimatedata', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data', '-tc', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml', '-i', '../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c', '-s', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf', '--cacsl2boogietranslator.entry.function', 'main', '--witnessprinter.witness.directory', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux', '--witnessprinter.witness.filename', 'witness', '--witnessprinter.write.witness.besides.input.file', 'false', '--witnessprinter.graph.data.specification', 'CHECK( init(main()), LTL(G ! call(reach_error())) )\n\n', '--witnessprinter.graph.data.producer', 'Automizer', '--witnessprinter.graph.data.architecture', '32bit', '--witnessprinter.graph.data.programhash', '008f13fd1550f54b25db8c20ee30759d3819e45d65744da9f4f77718b68e7e66'] Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 008f13fd1550f54b25db8c20ee30759d3819e45d65744da9f4f77718b68e7e66 --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 22:54:32,004 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 22:54:32,086 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-06 22:54:32,092 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 22:54:32,093 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 22:54:32,119 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 22:54:32,119 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 22:54:32,120 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 22:54:32,121 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 22:54:32,121 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 22:54:32,121 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 22:54:32,121 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 22:54:32,121 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 22:54:32,121 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 22:54:32,122 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 22:54:32,122 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 22:54:32,123 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 22:54:32,123 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:32,124 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 22:54:32,124 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 22:54:32,125 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 22:54:32,125 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 22:54:32,125 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 22:54:32,125 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 22:54:32,125 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 22:54:32,125 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 -> 008f13fd1550f54b25db8c20ee30759d3819e45d65744da9f4f77718b68e7e66 [2024-11-06 22:54:32,412 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 22:54:32,419 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 22:54:32,421 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 22:54:32,423 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 22:54:32,423 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 22:54:32,424 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c [2024-11-06 22:54:33,741 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 22:54:33,968 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 22:54:33,970 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c [2024-11-06 22:54:33,977 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/36b7ac292/7aa6bbec1cbd4d79baa84a97a897d568/FLAGa20acb499 [2024-11-06 22:54:33,989 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/36b7ac292/7aa6bbec1cbd4d79baa84a97a897d568 [2024-11-06 22:54:33,991 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 22:54:33,993 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 22:54:33,994 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:33,994 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 22:54:33,997 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 22:54:33,998 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:33" (1/1) ... [2024-11-06 22:54:33,999 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@36400450 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:33, skipping insertion in model container [2024-11-06 22:54:33,999 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:33" (1/1) ... [2024-11-06 22:54:34,012 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 22:54:34,142 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c[489,502] [2024-11-06 22:54:34,164 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:34,175 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 22:54:34,185 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound1.c[489,502] [2024-11-06 22:54:34,194 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:34,206 INFO L204 MainTranslator]: Completed translation [2024-11-06 22:54:34,207 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34 WrapperNode [2024-11-06 22:54:34,208 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:34,209 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:34,209 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 22:54:34,209 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 22:54:34,214 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,218 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,234 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 57 [2024-11-06 22:54:34,236 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:34,237 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 22:54:34,237 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 22:54:34,237 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 22:54:34,244 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,244 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,246 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,258 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-06 22:54:34,258 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,258 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,261 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,265 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,266 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,270 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,271 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 22:54:34,271 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 22:54:34,272 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 22:54:34,272 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 22:54:34,272 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (1/1) ... [2024-11-06 22:54:34,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:34,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:34,304 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) [2024-11-06 22:54:34,308 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 [2024-11-06 22:54:34,329 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 22:54:34,330 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-06 22:54:34,330 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-06 22:54:34,330 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 22:54:34,330 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 22:54:34,331 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 22:54:34,331 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 22:54:34,331 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 22:54:34,392 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 22:54:34,394 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 22:54:34,552 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-06 22:54:34,552 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 22:54:34,559 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 22:54:34,560 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-06 22:54:34,560 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:34 BoogieIcfgContainer [2024-11-06 22:54:34,560 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 22:54:34,562 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 22:54:34,563 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 22:54:34,567 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 22:54:34,567 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:54:33" (1/3) ... [2024-11-06 22:54:34,568 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b314ea6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:34, skipping insertion in model container [2024-11-06 22:54:34,568 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:34" (2/3) ... [2024-11-06 22:54:34,568 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b314ea6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:34, skipping insertion in model container [2024-11-06 22:54:34,568 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:34" (3/3) ... [2024-11-06 22:54:34,569 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound1.c [2024-11-06 22:54:34,582 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 22:54:34,582 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 22:54:34,634 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 22:54:34,646 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;@566b5c7a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 22:54:34,647 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 22:54:34,651 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-06 22:54:34,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-06 22:54:34,658 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:34,658 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:34,659 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:34,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:34,663 INFO L85 PathProgramCache]: Analyzing trace with hash 501437177, now seen corresponding path program 1 times [2024-11-06 22:54:34,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:34,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1123813695] [2024-11-06 22:54:34,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:34,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:34,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:34,776 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1010809040] [2024-11-06 22:54:34,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:34,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:34,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:34,780 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) [2024-11-06 22:54:34,784 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 [2024-11-06 22:54:34,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:34,862 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:34,866 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:34,988 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:34,988 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:34,989 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:34,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1123813695] [2024-11-06 22:54:34,990 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:34,990 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1010809040] [2024-11-06 22:54:34,991 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1010809040] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:34,991 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:34,991 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:34,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [781343111] [2024-11-06 22:54:34,994 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:34,998 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:34,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:35,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:35,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:35,032 INFO L87 Difference]: Start difference. First operand has 32 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:35,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:35,139 INFO L93 Difference]: Finished difference Result 77 states and 133 transitions. [2024-11-06 22:54:35,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:35,142 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2024-11-06 22:54:35,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:35,151 INFO L225 Difference]: With dead ends: 77 [2024-11-06 22:54:35,151 INFO L226 Difference]: Without dead ends: 42 [2024-11-06 22:54:35,155 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:35,157 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:35,158 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 136 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:35,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-06 22:54:35,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2024-11-06 22:54:35,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 20 states have (on average 1.25) internal successors, (25), 22 states have internal predecessors, (25), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-06 22:54:35,194 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 58 transitions. [2024-11-06 22:54:35,197 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 58 transitions. Word has length 29 [2024-11-06 22:54:35,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:35,197 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 58 transitions. [2024-11-06 22:54:35,197 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:35,198 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 58 transitions. [2024-11-06 22:54:35,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-06 22:54:35,199 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:35,199 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:35,213 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-06 22:54:35,400 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-06 22:54:35,400 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:35,401 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:35,401 INFO L85 PathProgramCache]: Analyzing trace with hash -1017640517, now seen corresponding path program 1 times [2024-11-06 22:54:35,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:35,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2130588028] [2024-11-06 22:54:35,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:35,401 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:35,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:35,431 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1443389027] [2024-11-06 22:54:35,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:35,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:35,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:35,434 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) [2024-11-06 22:54:35,436 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 [2024-11-06 22:54:35,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:35,500 INFO L255 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:35,502 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:35,568 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:35,568 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:35,568 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:35,568 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2130588028] [2024-11-06 22:54:35,568 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:35,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1443389027] [2024-11-06 22:54:35,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1443389027] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:35,569 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:35,569 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:35,569 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2066058044] [2024-11-06 22:54:35,569 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:35,570 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:35,571 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:35,571 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:35,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:35,572 INFO L87 Difference]: Start difference. First operand 41 states and 58 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-06 22:54:35,650 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:35,650 INFO L93 Difference]: Finished difference Result 66 states and 98 transitions. [2024-11-06 22:54:35,650 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:35,651 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2024-11-06 22:54:35,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:35,653 INFO L225 Difference]: With dead ends: 66 [2024-11-06 22:54:35,653 INFO L226 Difference]: Without dead ends: 64 [2024-11-06 22:54:35,653 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:35,654 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:35,655 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 123 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:35,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-06 22:54:35,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 57. [2024-11-06 22:54:35,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 31 states have internal predecessors, (38), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-06 22:54:35,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 83 transitions. [2024-11-06 22:54:35,675 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 83 transitions. Word has length 34 [2024-11-06 22:54:35,675 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:35,675 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 83 transitions. [2024-11-06 22:54:35,675 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-06 22:54:35,676 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 83 transitions. [2024-11-06 22:54:35,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-06 22:54:35,677 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:35,677 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:35,694 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-06 22:54:35,878 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:35,878 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:35,879 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:35,879 INFO L85 PathProgramCache]: Analyzing trace with hash 1133401081, now seen corresponding path program 1 times [2024-11-06 22:54:35,879 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:35,879 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1990763608] [2024-11-06 22:54:35,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:35,879 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:35,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:35,925 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [545581850] [2024-11-06 22:54:35,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:35,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:35,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:35,930 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) [2024-11-06 22:54:35,932 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 [2024-11-06 22:54:35,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:35,984 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-06 22:54:35,986 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:36,067 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-06 22:54:36,067 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:36,067 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:36,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1990763608] [2024-11-06 22:54:36,067 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:36,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [545581850] [2024-11-06 22:54:36,068 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [545581850] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:36,068 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:36,068 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:36,068 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1831647148] [2024-11-06 22:54:36,068 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:36,068 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:36,068 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:36,069 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:36,069 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:36,069 INFO L87 Difference]: Start difference. First operand 57 states and 83 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-06 22:54:36,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:36,140 INFO L93 Difference]: Finished difference Result 64 states and 89 transitions. [2024-11-06 22:54:36,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:36,141 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2024-11-06 22:54:36,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:36,142 INFO L225 Difference]: With dead ends: 64 [2024-11-06 22:54:36,142 INFO L226 Difference]: Without dead ends: 60 [2024-11-06 22:54:36,143 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:36,143 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:36,143 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 122 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:36,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-06 22:54:36,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2024-11-06 22:54:36,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 32 states have (on average 1.28125) internal successors, (41), 34 states have internal predecessors, (41), 22 states have call successors, (22), 5 states have call predecessors, (22), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-06 22:54:36,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 83 transitions. [2024-11-06 22:54:36,158 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 83 transitions. Word has length 39 [2024-11-06 22:54:36,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:36,158 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 83 transitions. [2024-11-06 22:54:36,158 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-06 22:54:36,158 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 83 transitions. [2024-11-06 22:54:36,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-06 22:54:36,159 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:36,159 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:36,177 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-06 22:54:36,360 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:36,361 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:36,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:36,361 INFO L85 PathProgramCache]: Analyzing trace with hash -1954831506, now seen corresponding path program 1 times [2024-11-06 22:54:36,361 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:36,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1871813864] [2024-11-06 22:54:36,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:36,361 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:36,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,573 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:36,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,577 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:36,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,580 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:36,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,582 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:36,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,585 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:36,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,592 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:36,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,598 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:36,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,604 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-06 22:54:36,604 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:36,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1871813864] [2024-11-06 22:54:36,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1871813864] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:36,605 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:36,607 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:36,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2142055734] [2024-11-06 22:54:36,607 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:36,607 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:36,607 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:36,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:36,608 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:36,608 INFO L87 Difference]: Start difference. First operand 60 states and 83 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-11-06 22:54:36,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:36,654 INFO L93 Difference]: Finished difference Result 66 states and 88 transitions. [2024-11-06 22:54:36,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:36,656 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2024-11-06 22:54:36,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:36,657 INFO L225 Difference]: With dead ends: 66 [2024-11-06 22:54:36,657 INFO L226 Difference]: Without dead ends: 64 [2024-11-06 22:54:36,657 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:36,658 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:36,658 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 132 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:36,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-06 22:54:36,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2024-11-06 22:54:36,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 37 states have internal predecessors, (44), 22 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-11-06 22:54:36,674 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2024-11-06 22:54:36,675 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 45 [2024-11-06 22:54:36,675 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:36,675 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2024-11-06 22:54:36,675 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-11-06 22:54:36,676 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2024-11-06 22:54:36,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-06 22:54:36,677 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:36,677 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:36,677 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-06 22:54:36,677 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:36,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:36,677 INFO L85 PathProgramCache]: Analyzing trace with hash -1265228631, now seen corresponding path program 1 times [2024-11-06 22:54:36,678 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:36,678 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [348386435] [2024-11-06 22:54:36,678 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:36,678 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:36,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,933 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:36,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,939 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:36,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,973 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:36,976 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,993 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:36,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:36,998 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:37,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,004 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:37,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,038 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:37,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,046 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:37,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:37,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [348386435] [2024-11-06 22:54:37,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [348386435] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:37,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1515850989] [2024-11-06 22:54:37,047 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:37,047 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:37,047 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:37,049 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) [2024-11-06 22:54:37,051 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 [2024-11-06 22:54:37,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,111 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:37,113 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:37,233 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2024-11-06 22:54:37,233 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:37,233 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1515850989] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:37,233 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:37,234 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 12 [2024-11-06 22:54:37,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1085777894] [2024-11-06 22:54:37,235 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:37,235 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:37,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:37,236 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:37,236 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2024-11-06 22:54:37,236 INFO L87 Difference]: Start difference. First operand 64 states and 86 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-06 22:54:37,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:37,300 INFO L93 Difference]: Finished difference Result 80 states and 104 transitions. [2024-11-06 22:54:37,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:37,301 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2024-11-06 22:54:37,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:37,303 INFO L225 Difference]: With dead ends: 80 [2024-11-06 22:54:37,304 INFO L226 Difference]: Without dead ends: 78 [2024-11-06 22:54:37,305 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:54:37,305 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:37,306 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 121 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:37,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-11-06 22:54:37,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 75. [2024-11-06 22:54:37,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 44 states have internal predecessors, (50), 25 states have call successors, (25), 8 states have call predecessors, (25), 8 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-06 22:54:37,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2024-11-06 22:54:37,328 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 47 [2024-11-06 22:54:37,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:37,328 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2024-11-06 22:54:37,328 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-06 22:54:37,328 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2024-11-06 22:54:37,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-06 22:54:37,331 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:37,331 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:37,347 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-06 22:54:37,531 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:37,532 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:37,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:37,532 INFO L85 PathProgramCache]: Analyzing trace with hash 1617953190, now seen corresponding path program 1 times [2024-11-06 22:54:37,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:37,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [213595140] [2024-11-06 22:54:37,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:37,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:37,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,721 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:37,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,724 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:37,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:37,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,730 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:37,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,732 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:37,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:37,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,767 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:37,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,786 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-06 22:54:37,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,794 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:37,795 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:37,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [213595140] [2024-11-06 22:54:37,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [213595140] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:37,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1003176585] [2024-11-06 22:54:37,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:37,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:37,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:37,798 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) [2024-11-06 22:54:37,800 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 [2024-11-06 22:54:37,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:37,857 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:37,859 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:37,970 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:54:37,970 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:37,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1003176585] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:37,970 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:37,971 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-11-06 22:54:37,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026498939] [2024-11-06 22:54:37,971 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:37,971 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:54:37,971 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:37,972 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:54:37,972 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-06 22:54:37,972 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-06 22:54:38,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:38,075 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2024-11-06 22:54:38,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:54:38,076 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2024-11-06 22:54:38,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:38,077 INFO L225 Difference]: With dead ends: 88 [2024-11-06 22:54:38,077 INFO L226 Difference]: Without dead ends: 84 [2024-11-06 22:54:38,077 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:54:38,078 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:38,080 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 147 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:38,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-11-06 22:54:38,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 83. [2024-11-06 22:54:38,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 47 states have (on average 1.1702127659574468) internal successors, (55), 50 states have internal predecessors, (55), 25 states have call successors, (25), 10 states have call predecessors, (25), 10 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-06 22:54:38,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 103 transitions. [2024-11-06 22:54:38,094 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 103 transitions. Word has length 50 [2024-11-06 22:54:38,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:38,094 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 103 transitions. [2024-11-06 22:54:38,094 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-06 22:54:38,095 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 103 transitions. [2024-11-06 22:54:38,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-06 22:54:38,096 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:38,096 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:38,114 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-06 22:54:38,301 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:38,302 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:38,302 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:38,303 INFO L85 PathProgramCache]: Analyzing trace with hash 860577929, now seen corresponding path program 1 times [2024-11-06 22:54:38,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:38,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1482400451] [2024-11-06 22:54:38,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:38,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:38,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,452 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:38,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,474 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:38,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:38,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:38,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,492 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:38,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,496 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:38,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,499 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:38,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,503 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:54:38,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,504 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 17 proven. 6 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-06 22:54:38,505 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:38,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1482400451] [2024-11-06 22:54:38,505 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1482400451] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:38,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2026902063] [2024-11-06 22:54:38,505 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:38,505 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:38,505 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:38,507 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:38,509 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-06 22:54:38,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:38,560 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-06 22:54:38,562 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:38,667 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 27 proven. 6 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-06 22:54:38,667 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:38,805 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 17 proven. 6 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-06 22:54:38,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2026902063] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:38,806 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:54:38,806 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 14 [2024-11-06 22:54:38,806 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1863232123] [2024-11-06 22:54:38,807 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:38,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-06 22:54:38,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:38,809 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-06 22:54:38,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:54:38,809 INFO L87 Difference]: Start difference. First operand 83 states and 103 transitions. Second operand has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-06 22:54:38,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:38,908 INFO L93 Difference]: Finished difference Result 107 states and 132 transitions. [2024-11-06 22:54:38,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 22:54:38,909 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) Word has length 52 [2024-11-06 22:54:38,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:38,910 INFO L225 Difference]: With dead ends: 107 [2024-11-06 22:54:38,910 INFO L226 Difference]: Without dead ends: 71 [2024-11-06 22:54:38,911 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 113 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2024-11-06 22:54:38,911 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 18 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:38,911 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 160 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:38,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-06 22:54:38,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2024-11-06 22:54:38,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.1219512195121952) internal successors, (46), 43 states have internal predecessors, (46), 20 states have call successors, (20), 9 states have call predecessors, (20), 9 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-06 22:54:38,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2024-11-06 22:54:38,923 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 52 [2024-11-06 22:54:38,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:38,924 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2024-11-06 22:54:38,924 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 11 states have internal predecessors, (34), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-06 22:54:38,924 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2024-11-06 22:54:38,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-06 22:54:38,926 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:38,926 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:38,942 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-06 22:54:39,126 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-06 22:54:39,127 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:39,127 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:39,127 INFO L85 PathProgramCache]: Analyzing trace with hash -1226126935, now seen corresponding path program 2 times [2024-11-06 22:54:39,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:39,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986400972] [2024-11-06 22:54:39,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:39,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:39,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:39,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,260 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:39,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,279 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:39,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,290 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:39,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,293 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:39,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,295 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:39,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,299 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:39,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,301 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:54:39,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,303 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-11-06 22:54:39,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:39,305 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 20 proven. 6 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-06 22:54:39,305 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:39,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986400972] [2024-11-06 22:54:39,305 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [986400972] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:39,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343166970] [2024-11-06 22:54:39,306 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-06 22:54:39,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:39,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:39,308 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:39,309 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-06 22:54:39,357 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-06 22:54:39,358 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:54:39,359 INFO L255 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-06 22:54:39,360 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:39,466 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 40 proven. 6 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-06 22:54:39,466 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:39,576 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 20 proven. 6 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-06 22:54:39,577 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343166970] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:39,577 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:54:39,577 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 13 [2024-11-06 22:54:39,577 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [645551718] [2024-11-06 22:54:39,577 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:39,577 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-06 22:54:39,577 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:39,578 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-06 22:54:39,578 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:54:39,578 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 13 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 8 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-06 22:54:39,663 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:39,663 INFO L93 Difference]: Finished difference Result 75 states and 88 transitions. [2024-11-06 22:54:39,663 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 22:54:39,664 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 8 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) Word has length 57 [2024-11-06 22:54:39,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:39,664 INFO L225 Difference]: With dead ends: 75 [2024-11-06 22:54:39,664 INFO L226 Difference]: Without dead ends: 0 [2024-11-06 22:54:39,665 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 124 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=53, Invalid=157, Unknown=0, NotChecked=0, Total=210 [2024-11-06 22:54:39,665 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:39,665 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 116 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:39,666 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-06 22:54:39,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-06 22:54:39,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-06 22:54:39,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-06 22:54:39,666 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 57 [2024-11-06 22:54:39,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:39,666 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-06 22:54:39,667 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.5454545454545454) internal successors, (28), 9 states have internal predecessors, (28), 8 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-06 22:54:39,667 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-06 22:54:39,667 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-06 22:54:39,670 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-06 22:54:39,687 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-06 22:54:39,874 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:39,877 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:39,878 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-06 22:54:40,090 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-06 22:54:40,108 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.11 10:54:40 BoogieIcfgContainer [2024-11-06 22:54:40,108 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-06 22:54:40,109 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-06 22:54:40,109 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-06 22:54:40,109 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-06 22:54:40,110 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:34" (3/4) ... [2024-11-06 22:54:40,111 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-06 22:54:40,116 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-11-06 22:54:40,116 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-06 22:54:40,120 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-11-06 22:54:40,120 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-06 22:54:40,120 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-06 22:54:40,120 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-06 22:54:40,187 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-06 22:54:40,187 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-06 22:54:40,187 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-06 22:54:40,188 INFO L158 Benchmark]: Toolchain (without parser) took 6195.06ms. Allocated memory was 117.4MB in the beginning and 176.2MB in the end (delta: 58.7MB). Free memory was 91.3MB in the beginning and 55.7MB in the end (delta: 35.6MB). Peak memory consumption was 89.3MB. Max. memory is 16.1GB. [2024-11-06 22:54:40,188 INFO L158 Benchmark]: CDTParser took 0.32ms. Allocated memory is still 117.4MB. Free memory is still 81.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:40,189 INFO L158 Benchmark]: CACSL2BoogieTranslator took 214.22ms. Allocated memory is still 117.4MB. Free memory was 91.1MB in the beginning and 79.8MB in the end (delta: 11.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:54:40,189 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.48ms. Allocated memory is still 117.4MB. Free memory was 79.8MB in the beginning and 78.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:40,190 INFO L158 Benchmark]: Boogie Preprocessor took 34.16ms. Allocated memory is still 117.4MB. Free memory was 78.5MB in the beginning and 77.4MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:54:40,190 INFO L158 Benchmark]: RCFGBuilder took 288.82ms. Allocated memory is still 117.4MB. Free memory was 77.4MB in the beginning and 66.7MB in the end (delta: 10.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:54:40,190 INFO L158 Benchmark]: TraceAbstraction took 5545.99ms. Allocated memory was 117.4MB in the beginning and 176.2MB in the end (delta: 58.7MB). Free memory was 66.2MB in the beginning and 60.6MB in the end (delta: 5.5MB). Peak memory consumption was 64.1MB. Max. memory is 16.1GB. [2024-11-06 22:54:40,191 INFO L158 Benchmark]: Witness Printer took 78.14ms. Allocated memory is still 176.2MB. Free memory was 60.6MB in the beginning and 55.7MB in the end (delta: 4.9MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:40,192 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.32ms. Allocated memory is still 117.4MB. Free memory is still 81.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 214.22ms. Allocated memory is still 117.4MB. Free memory was 91.1MB in the beginning and 79.8MB in the end (delta: 11.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.48ms. Allocated memory is still 117.4MB. Free memory was 79.8MB in the beginning and 78.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 34.16ms. Allocated memory is still 117.4MB. Free memory was 78.5MB in the beginning and 77.4MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 288.82ms. Allocated memory is still 117.4MB. Free memory was 77.4MB in the beginning and 66.7MB in the end (delta: 10.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 5545.99ms. Allocated memory was 117.4MB in the beginning and 176.2MB in the end (delta: 58.7MB). Free memory was 66.2MB in the beginning and 60.6MB in the end (delta: 5.5MB). Peak memory consumption was 64.1MB. Max. memory is 16.1GB. * Witness Printer took 78.14ms. Allocated memory is still 176.2MB. Free memory was 60.6MB in the beginning and 55.7MB in the end (delta: 4.9MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 5.3s, OverallIterations: 8, TraceHistogramMax: 6, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 0.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 80 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 55 mSDsluCounter, 1057 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 802 mSDsCounter, 40 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 329 IncrementalHoareTripleChecker+Invalid, 369 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 40 mSolverCounterUnsat, 255 mSDtfsCounter, 329 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 536 GetRequests, 467 SyntacticMatches, 4 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=83occurred in iteration=6, InterpolantAutomatonStates: 47, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 12 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 2.1s InterpolantComputationTime, 661 NumberOfCodeBlocks, 661 NumberOfCodeBlocksAsserted, 16 NumberOfCheckSat, 654 ConstructedInterpolants, 0 QuantifiedInterpolants, 1486 SizeOfPredicates, 13 NumberOfNonLiveVariables, 781 ConjunctsInSsa, 79 ConjunctsInUnsatCore, 14 InterpolantComputations, 6 PerfectInterpolantSequences, 686/735 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 35]: Loop Invariant Derived loop invariant: ((((((((p == 1) && (b == y)) && (x == 1)) && (r == 0)) && (q == 0)) && (y == 1)) && (a == x)) && (s == 1)) - ProcedureContractResult [Line: 7]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (cond != 0) - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-11-06 22:54:40,223 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE