./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound50.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_valuebound50.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', '3134c54bcf8aadaf562f6870f2277db1ec6f958b1ed6dba99e7410745dba79ba'] 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_valuebound50.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 3134c54bcf8aadaf562f6870f2277db1ec6f958b1ed6dba99e7410745dba79ba --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 22:54:43,851 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 22:54:43,927 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:43,931 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 22:54:43,931 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 22:54:43,952 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 22:54:43,953 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 22:54:43,954 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 22:54:43,954 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 22:54:43,954 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 22:54:43,955 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 22:54:43,955 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 22:54:43,955 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 22:54:43,955 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 22:54:43,956 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 22:54:43,956 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 22:54:43,956 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 22:54:43,956 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 22:54:43,956 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 22:54:43,957 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 22:54:43,957 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 22:54:43,958 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 22:54:43,958 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 22:54:43,958 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 22:54:43,958 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:43,958 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 22:54:43,959 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 22:54:43,959 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 -> 3134c54bcf8aadaf562f6870f2277db1ec6f958b1ed6dba99e7410745dba79ba [2024-11-06 22:54:44,189 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 22:54:44,194 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 22:54:44,196 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 22:54:44,197 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 22:54:44,197 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 22:54:44,198 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_valuebound50.c [2024-11-06 22:54:45,323 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 22:54:45,482 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 22:54:45,484 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound50.c [2024-11-06 22:54:45,493 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/99349982f/306550633602462c8eb2ca86844f8f9a/FLAG3bf377485 [2024-11-06 22:54:45,877 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/99349982f/306550633602462c8eb2ca86844f8f9a [2024-11-06 22:54:45,878 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 22:54:45,880 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 22:54:45,882 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:45,882 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 22:54:45,885 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 22:54:45,885 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:45" (1/1) ... [2024-11-06 22:54:45,886 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a2d180e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:45, skipping insertion in model container [2024-11-06 22:54:45,886 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:45" (1/1) ... [2024-11-06 22:54:45,897 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 22:54:45,986 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_valuebound50.c[489,502] [2024-11-06 22:54:45,999 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:46,008 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 22:54:46,016 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_valuebound50.c[489,502] [2024-11-06 22:54:46,023 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:46,033 INFO L204 MainTranslator]: Completed translation [2024-11-06 22:54:46,034 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:46 WrapperNode [2024-11-06 22:54:46,034 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:46,035 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:46,035 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 22:54:46,036 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 22:54:46,040 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:46" (1/1) ... [2024-11-06 22:54:46,044 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:46" (1/1) ... [2024-11-06 22:54:46,058 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 57 [2024-11-06 22:54:46,058 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:46,058 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 22:54:46,059 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 22:54:46,059 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 22:54:46,065 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:46" (1/1) ... [2024-11-06 22:54:46,065 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:46" (1/1) ... [2024-11-06 22:54:46,066 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:46" (1/1) ... [2024-11-06 22:54:46,076 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:46,077 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:46" (1/1) ... [2024-11-06 22:54:46,077 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:46" (1/1) ... [2024-11-06 22:54:46,080 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:46" (1/1) ... [2024-11-06 22:54:46,083 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:46" (1/1) ... [2024-11-06 22:54:46,087 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:46" (1/1) ... [2024-11-06 22:54:46,087 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:46" (1/1) ... [2024-11-06 22:54:46,088 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 22:54:46,089 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 22:54:46,089 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 22:54:46,089 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 22:54:46,090 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:46" (1/1) ... [2024-11-06 22:54:46,095 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:46,105 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:46,114 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:46,116 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:46,131 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 22:54:46,131 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-06 22:54:46,131 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-06 22:54:46,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 22:54:46,131 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 22:54:46,131 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 22:54:46,131 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 22:54:46,131 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 22:54:46,176 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 22:54:46,177 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 22:54:46,261 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-06 22:54:46,261 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 22:54:46,267 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 22:54:46,267 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-06 22:54:46,268 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:46 BoogieIcfgContainer [2024-11-06 22:54:46,268 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 22:54:46,269 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 22:54:46,269 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 22:54:46,273 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 22:54:46,273 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:54:45" (1/3) ... [2024-11-06 22:54:46,274 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@351dbe22 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:46, skipping insertion in model container [2024-11-06 22:54:46,274 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:46" (2/3) ... [2024-11-06 22:54:46,274 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@351dbe22 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:46, skipping insertion in model container [2024-11-06 22:54:46,274 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:46" (3/3) ... [2024-11-06 22:54:46,275 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound50.c [2024-11-06 22:54:46,285 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 22:54:46,285 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 22:54:46,325 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 22:54:46,335 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;@47bbcfe2, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 22:54:46,336 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 22:54:46,340 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:46,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-06 22:54:46,345 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:46,346 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:46,346 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:46,349 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:46,349 INFO L85 PathProgramCache]: Analyzing trace with hash 501437177, now seen corresponding path program 1 times [2024-11-06 22:54:46,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:46,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1674149852] [2024-11-06 22:54:46,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:46,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:46,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:46,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [466000066] [2024-11-06 22:54:46,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:46,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:46,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:46,440 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:46,441 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:46,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:46,498 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:46,502 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:46,614 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:46,614 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:46,615 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:46,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1674149852] [2024-11-06 22:54:46,616 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:46,616 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [466000066] [2024-11-06 22:54:46,617 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [466000066] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:46,617 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:46,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:46,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2058000413] [2024-11-06 22:54:46,619 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:46,622 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:46,622 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:46,645 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:46,645 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:46,647 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:46,723 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:46,724 INFO L93 Difference]: Finished difference Result 77 states and 133 transitions. [2024-11-06 22:54:46,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:46,727 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:46,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:46,732 INFO L225 Difference]: With dead ends: 77 [2024-11-06 22:54:46,733 INFO L226 Difference]: Without dead ends: 42 [2024-11-06 22:54:46,735 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:46,739 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:46,740 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.0s Time] [2024-11-06 22:54:46,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-06 22:54:46,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2024-11-06 22:54:46,770 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:46,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 58 transitions. [2024-11-06 22:54:46,776 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 58 transitions. Word has length 29 [2024-11-06 22:54:46,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:46,777 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 58 transitions. [2024-11-06 22:54:46,777 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:46,777 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 58 transitions. [2024-11-06 22:54:46,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-06 22:54:46,779 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:46,779 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:46,796 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-06 22:54:46,980 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:46,980 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:46,980 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:46,981 INFO L85 PathProgramCache]: Analyzing trace with hash -1017640517, now seen corresponding path program 1 times [2024-11-06 22:54:46,981 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:46,981 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [825146223] [2024-11-06 22:54:46,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:46,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:47,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:47,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [103544030] [2024-11-06 22:54:47,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:47,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:47,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:47,010 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:47,011 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:47,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,056 INFO L255 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:47,058 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:47,117 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:47,118 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:47,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:47,118 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [825146223] [2024-11-06 22:54:47,118 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:47,118 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [103544030] [2024-11-06 22:54:47,118 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [103544030] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:47,118 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:47,118 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:47,118 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1140815779] [2024-11-06 22:54:47,119 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:47,119 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:47,119 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:47,119 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:47,120 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:47,120 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:47,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:47,186 INFO L93 Difference]: Finished difference Result 66 states and 98 transitions. [2024-11-06 22:54:47,187 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:47,187 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:47,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:47,189 INFO L225 Difference]: With dead ends: 66 [2024-11-06 22:54:47,189 INFO L226 Difference]: Without dead ends: 64 [2024-11-06 22:54:47,190 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:47,191 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:47,191 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.0s Time] [2024-11-06 22:54:47,191 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-06 22:54:47,202 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 57. [2024-11-06 22:54:47,203 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:47,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 83 transitions. [2024-11-06 22:54:47,204 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 83 transitions. Word has length 34 [2024-11-06 22:54:47,205 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:47,205 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 83 transitions. [2024-11-06 22:54:47,205 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:47,205 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 83 transitions. [2024-11-06 22:54:47,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-06 22:54:47,206 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:47,206 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:47,220 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:47,406 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:47,407 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:47,408 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:47,408 INFO L85 PathProgramCache]: Analyzing trace with hash 1133401081, now seen corresponding path program 1 times [2024-11-06 22:54:47,408 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:47,408 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [732246314] [2024-11-06 22:54:47,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:47,408 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:47,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:47,428 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [190487347] [2024-11-06 22:54:47,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:47,428 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:47,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:47,433 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:47,434 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:47,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,474 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-06 22:54:47,476 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:47,532 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:47,533 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:47,533 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:47,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [732246314] [2024-11-06 22:54:47,533 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:47,533 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [190487347] [2024-11-06 22:54:47,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [190487347] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:47,533 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:47,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:47,533 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1730734798] [2024-11-06 22:54:47,534 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:47,534 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:47,534 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:47,534 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:47,536 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:47,536 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:47,586 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:47,586 INFO L93 Difference]: Finished difference Result 64 states and 89 transitions. [2024-11-06 22:54:47,586 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:47,586 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:47,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:47,587 INFO L225 Difference]: With dead ends: 64 [2024-11-06 22:54:47,587 INFO L226 Difference]: Without dead ends: 60 [2024-11-06 22:54:47,587 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:47,588 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:47,588 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.0s Time] [2024-11-06 22:54:47,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-06 22:54:47,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2024-11-06 22:54:47,598 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:47,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 83 transitions. [2024-11-06 22:54:47,600 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 83 transitions. Word has length 39 [2024-11-06 22:54:47,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:47,600 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 83 transitions. [2024-11-06 22:54:47,600 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:47,600 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 83 transitions. [2024-11-06 22:54:47,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-06 22:54:47,601 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:47,601 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:47,616 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:47,806 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:47,807 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:47,807 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:47,807 INFO L85 PathProgramCache]: Analyzing trace with hash -1954831506, now seen corresponding path program 1 times [2024-11-06 22:54:47,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:47,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [479744206] [2024-11-06 22:54:47,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:47,807 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:47,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,970 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:47,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,974 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:47,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,979 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:47,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,984 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:47,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,989 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:47,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,993 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:47,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:47,997 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:47,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,001 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:48,001 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:48,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [479744206] [2024-11-06 22:54:48,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [479744206] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:48,002 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:48,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:48,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [604103774] [2024-11-06 22:54:48,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:48,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:48,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:48,003 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:48,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:48,003 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:48,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:48,039 INFO L93 Difference]: Finished difference Result 66 states and 88 transitions. [2024-11-06 22:54:48,040 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:48,040 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:48,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:48,041 INFO L225 Difference]: With dead ends: 66 [2024-11-06 22:54:48,041 INFO L226 Difference]: Without dead ends: 64 [2024-11-06 22:54:48,041 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:48,041 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:48,041 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:48,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-06 22:54:48,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2024-11-06 22:54:48,051 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:48,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2024-11-06 22:54:48,053 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 45 [2024-11-06 22:54:48,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:48,054 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2024-11-06 22:54:48,054 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:48,054 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2024-11-06 22:54:48,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-06 22:54:48,055 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:48,055 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:48,056 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-06 22:54:48,056 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:48,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:48,056 INFO L85 PathProgramCache]: Analyzing trace with hash -1265228631, now seen corresponding path program 1 times [2024-11-06 22:54:48,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:48,056 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [280038630] [2024-11-06 22:54:48,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:48,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:48,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:48,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [648694934] [2024-11-06 22:54:48,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:48,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:48,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:48,082 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:48,083 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:48,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,119 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:48,120 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:48,183 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:48,184 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:48,184 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:48,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [280038630] [2024-11-06 22:54:48,184 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:48,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [648694934] [2024-11-06 22:54:48,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [648694934] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:48,185 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:48,185 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:48,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [384316901] [2024-11-06 22:54:48,185 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:48,185 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:48,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:48,186 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:48,186 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:48,187 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:48,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:48,232 INFO L93 Difference]: Finished difference Result 80 states and 104 transitions. [2024-11-06 22:54:48,232 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:48,232 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:48,233 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:48,233 INFO L225 Difference]: With dead ends: 80 [2024-11-06 22:54:48,233 INFO L226 Difference]: Without dead ends: 78 [2024-11-06 22:54:48,234 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 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:48,235 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:48,235 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:48,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-11-06 22:54:48,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 75. [2024-11-06 22:54:48,249 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:48,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2024-11-06 22:54:48,250 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 47 [2024-11-06 22:54:48,250 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:48,250 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2024-11-06 22:54:48,250 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:48,250 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2024-11-06 22:54:48,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-06 22:54:48,253 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:48,254 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:48,265 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:48,456 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:48,457 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:48,457 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:48,457 INFO L85 PathProgramCache]: Analyzing trace with hash 1617953190, now seen corresponding path program 1 times [2024-11-06 22:54:48,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:48,457 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1683724162] [2024-11-06 22:54:48,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:48,457 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:48,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,655 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:48,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,657 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:48,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,660 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:48,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,662 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:48,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,664 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:48,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,666 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:48,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,688 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:48,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,702 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-06 22:54:48,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,708 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:48,708 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:48,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1683724162] [2024-11-06 22:54:48,708 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1683724162] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:48,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1298323467] [2024-11-06 22:54:48,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:48,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:48,709 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:48,711 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:48,712 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:48,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:48,760 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:48,762 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:48,860 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:48,860 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:48,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1298323467] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:48,861 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:48,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-11-06 22:54:48,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354170186] [2024-11-06 22:54:48,861 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:48,862 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:54:48,862 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:48,862 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:54:48,863 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-06 22:54:48,863 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:48,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:48,937 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2024-11-06 22:54:48,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:54:48,938 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:48,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:48,939 INFO L225 Difference]: With dead ends: 88 [2024-11-06 22:54:48,939 INFO L226 Difference]: Without dead ends: 84 [2024-11-06 22:54:48,939 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:48,940 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:48,940 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.0s Time] [2024-11-06 22:54:48,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-11-06 22:54:48,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 83. [2024-11-06 22:54:48,951 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:48,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 103 transitions. [2024-11-06 22:54:48,952 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 103 transitions. Word has length 50 [2024-11-06 22:54:48,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:48,953 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 103 transitions. [2024-11-06 22:54:48,953 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:48,953 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 103 transitions. [2024-11-06 22:54:48,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-11-06 22:54:48,954 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:48,954 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:48,970 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:49,158 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:49,159 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:49,159 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:49,159 INFO L85 PathProgramCache]: Analyzing trace with hash 860577929, now seen corresponding path program 1 times [2024-11-06 22:54:49,159 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:49,159 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339979271] [2024-11-06 22:54:49,159 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:49,159 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:49,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:49,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [510055436] [2024-11-06 22:54:49,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:49,175 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:49,177 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:49,179 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:49,180 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:49,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:49,219 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-06 22:54:49,220 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:49,380 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:49,380 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:49,581 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:49,581 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:49,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [339979271] [2024-11-06 22:54:49,581 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:49,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [510055436] [2024-11-06 22:54:49,582 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [510055436] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:49,582 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 22:54:49,582 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-11-06 22:54:49,582 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [474181804] [2024-11-06 22:54:49,582 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:49,582 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-06 22:54:49,582 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:49,583 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-06 22:54:49,583 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:54:49,583 INFO L87 Difference]: Start difference. First operand 83 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-06 22:54:49,987 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:49,988 INFO L93 Difference]: Finished difference Result 107 states and 140 transitions. [2024-11-06 22:54:49,988 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-06 22:54:49,988 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 52 [2024-11-06 22:54:49,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:49,989 INFO L225 Difference]: With dead ends: 107 [2024-11-06 22:54:49,989 INFO L226 Difference]: Without dead ends: 92 [2024-11-06 22:54:49,989 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2024-11-06 22:54:49,990 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 16 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:49,990 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 211 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 22:54:49,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-06 22:54:50,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 75. [2024-11-06 22:54:50,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 46 states have internal predecessors, (51), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-06 22:54:50,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 91 transitions. [2024-11-06 22:54:50,002 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 91 transitions. Word has length 52 [2024-11-06 22:54:50,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:50,002 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 91 transitions. [2024-11-06 22:54:50,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-06 22:54:50,002 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 91 transitions. [2024-11-06 22:54:50,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-06 22:54:50,003 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:50,003 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:50,016 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:50,203 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:50,203 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:50,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:50,204 INFO L85 PathProgramCache]: Analyzing trace with hash 1236716699, now seen corresponding path program 1 times [2024-11-06 22:54:50,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:50,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8049538] [2024-11-06 22:54:50,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:50,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:50,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:50,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [83667867] [2024-11-06 22:54:50,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:50,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:50,219 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:50,221 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:50,223 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:50,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,274 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-06 22:54:50,286 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:50,423 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-06 22:54:50,424 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:50,507 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-11-06 22:54:50,508 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:50,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [8049538] [2024-11-06 22:54:50,508 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:50,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [83667867] [2024-11-06 22:54:50,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [83667867] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:50,508 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:50,508 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2024-11-06 22:54:50,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [264204153] [2024-11-06 22:54:50,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:50,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:50,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:50,509 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:50,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:54:50,509 INFO L87 Difference]: Start difference. First operand 75 states and 91 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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:50,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:50,589 INFO L93 Difference]: Finished difference Result 81 states and 96 transitions. [2024-11-06 22:54:50,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:50,589 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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 65 [2024-11-06 22:54:50,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:50,590 INFO L225 Difference]: With dead ends: 81 [2024-11-06 22:54:50,590 INFO L226 Difference]: Without dead ends: 76 [2024-11-06 22:54:50,590 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-06 22:54:50,591 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 4 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:50,591 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 109 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:50,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-06 22:54:50,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 74. [2024-11-06 22:54:50,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 46 states have (on average 1.1304347826086956) internal successors, (52), 46 states have internal predecessors, (52), 18 states have call successors, (18), 10 states have call predecessors, (18), 9 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2024-11-06 22:54:50,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 87 transitions. [2024-11-06 22:54:50,606 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 87 transitions. Word has length 65 [2024-11-06 22:54:50,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:50,607 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 87 transitions. [2024-11-06 22:54:50,607 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 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:50,607 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 87 transitions. [2024-11-06 22:54:50,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-06 22:54:50,607 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:50,608 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:50,620 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-06 22:54:50,808 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:50,808 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:50,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:50,809 INFO L85 PathProgramCache]: Analyzing trace with hash -2086142860, now seen corresponding path program 1 times [2024-11-06 22:54:50,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:50,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [458082539] [2024-11-06 22:54:50,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:50,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:50,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:50,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 22:54:50,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:50,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,955 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:50,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,956 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-11-06 22:54:50,956 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-06 22:54:50,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,962 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-06 22:54:50,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,965 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:54:50,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-11-06 22:54:50,968 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:50,993 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-11-06 22:54:50,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:51,000 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-11-06 22:54:51,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:51,003 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-06 22:54:51,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:51,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [458082539] [2024-11-06 22:54:51,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [458082539] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:51,003 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1474782069] [2024-11-06 22:54:51,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:51,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:51,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:51,005 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:51,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-06 22:54:51,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:51,047 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-06 22:54:51,048 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:51,091 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-06 22:54:51,091 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:51,168 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-06 22:54:51,168 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1474782069] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:51,168 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:54:51,168 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2024-11-06 22:54:51,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [74232509] [2024-11-06 22:54:51,168 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:51,168 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-06 22:54:51,168 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:51,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-06 22:54:51,169 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-11-06 22:54:51,169 INFO L87 Difference]: Start difference. First operand 74 states and 87 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-06 22:54:51,272 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:51,273 INFO L93 Difference]: Finished difference Result 81 states and 95 transitions. [2024-11-06 22:54:51,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 22:54:51,274 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 68 [2024-11-06 22:54:51,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:51,275 INFO L225 Difference]: With dead ends: 81 [2024-11-06 22:54:51,275 INFO L226 Difference]: Without dead ends: 0 [2024-11-06 22:54:51,275 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 153 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-11-06 22:54:51,275 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 7 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 87 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:51,276 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 141 Invalid, 87 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:51,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-06 22:54:51,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-06 22:54:51,276 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:51,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-06 22:54:51,276 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 68 [2024-11-06 22:54:51,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:51,276 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-06 22:54:51,276 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-06 22:54:51,276 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-06 22:54:51,276 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-06 22:54:51,279 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-06 22:54:51,292 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-06 22:54:51,479 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:51,482 INFO L407 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:51,483 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-06 22:54:56,416 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-06 22:54:56,430 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.11 10:54:56 BoogieIcfgContainer [2024-11-06 22:54:56,430 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-06 22:54:56,431 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-06 22:54:56,431 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-06 22:54:56,431 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-06 22:54:56,431 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:46" (3/4) ... [2024-11-06 22:54:56,433 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-11-06 22:54:56,436 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-11-06 22:54:56,437 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-06 22:54:56,439 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-11-06 22:54:56,439 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-06 22:54:56,439 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-11-06 22:54:56,439 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-06 22:54:56,494 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-06 22:54:56,494 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-06 22:54:56,494 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-06 22:54:56,494 INFO L158 Benchmark]: Toolchain (without parser) took 10614.70ms. Allocated memory was 117.4MB in the beginning and 151.0MB in the end (delta: 33.6MB). Free memory was 93.1MB in the beginning and 122.6MB in the end (delta: -29.5MB). Peak memory consumption was 81.0MB. Max. memory is 16.1GB. [2024-11-06 22:54:56,495 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 117.4MB. Free memory is still 81.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:56,495 INFO L158 Benchmark]: CACSL2BoogieTranslator took 153.24ms. Allocated memory is still 117.4MB. Free memory was 92.9MB in the beginning and 81.7MB in the end (delta: 11.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-06 22:54:56,495 INFO L158 Benchmark]: Boogie Procedure Inliner took 22.94ms. Allocated memory is still 117.4MB. Free memory was 81.7MB in the beginning and 80.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:56,495 INFO L158 Benchmark]: Boogie Preprocessor took 29.94ms. Allocated memory is still 117.4MB. Free memory was 80.5MB in the beginning and 79.3MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-06 22:54:56,495 INFO L158 Benchmark]: RCFGBuilder took 178.81ms. Allocated memory is still 117.4MB. Free memory was 79.3MB in the beginning and 68.6MB in the end (delta: 10.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2024-11-06 22:54:56,496 INFO L158 Benchmark]: TraceAbstraction took 10161.16ms. Allocated memory was 117.4MB in the beginning and 151.0MB in the end (delta: 33.6MB). Free memory was 68.1MB in the beginning and 53.1MB in the end (delta: 14.9MB). Peak memory consumption was 55.7MB. Max. memory is 16.1GB. [2024-11-06 22:54:56,496 INFO L158 Benchmark]: Witness Printer took 63.17ms. Allocated memory is still 151.0MB. Free memory was 53.1MB in the beginning and 122.6MB in the end (delta: -69.4MB). Peak memory consumption was 9.0MB. Max. memory is 16.1GB. [2024-11-06 22:54:56,498 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.18ms. Allocated memory is still 117.4MB. Free memory is still 81.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 153.24ms. Allocated memory is still 117.4MB. Free memory was 92.9MB in the beginning and 81.7MB in the end (delta: 11.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 22.94ms. Allocated memory is still 117.4MB. Free memory was 81.7MB in the beginning and 80.5MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 29.94ms. Allocated memory is still 117.4MB. Free memory was 80.5MB in the beginning and 79.3MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 178.81ms. Allocated memory is still 117.4MB. Free memory was 79.3MB in the beginning and 68.6MB in the end (delta: 10.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * TraceAbstraction took 10161.16ms. Allocated memory was 117.4MB in the beginning and 151.0MB in the end (delta: 33.6MB). Free memory was 68.1MB in the beginning and 53.1MB in the end (delta: 14.9MB). Peak memory consumption was 55.7MB. Max. memory is 16.1GB. * Witness Printer took 63.17ms. Allocated memory is still 151.0MB. Free memory was 53.1MB in the beginning and 122.6MB in the end (delta: -69.4MB). Peak memory consumption was 9.0MB. 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.2s, OverallIterations: 9, TraceHistogramMax: 8, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 1.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 83 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 58 mSDsluCounter, 1242 SdHoareTripleChecker+Invalid, 0.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 950 mSDsCounter, 60 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 477 IncrementalHoareTripleChecker+Invalid, 537 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 60 mSolverCounterUnsat, 292 mSDtfsCounter, 477 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 645 GetRequests, 578 SyntacticMatches, 4 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=83occurred in iteration=6, InterpolantAutomatonStates: 53, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 31 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.7s InterpolantComputationTime, 813 NumberOfCodeBlocks, 813 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 718 ConstructedInterpolants, 0 QuantifiedInterpolants, 1930 SizeOfPredicates, 14 NumberOfNonLiveVariables, 956 ConjunctsInSsa, 110 ConjunctsInUnsatCore, 14 InterpolantComputations, 7 PerfectInterpolantSequences, 933/991 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: (((((__int128) p * s) == (((__int128) q * r) + 1)) && (((((__int128) r * y) + b) + ((__int128) p * x)) == ((a + ((__int128) s * y)) + ((__int128) q * x)))) && ((((__int128) r * y) + ((__int128) p * x)) == a)) - 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:56,514 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE