./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.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/recursified_nla-digbench/recursified_cohencu-ll.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', '260777f6a7be1f16cc330a008300c11ebdea8f1cf9d8e96a0325274fd8fd5b2a'] 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/recursified_nla-digbench/recursified_cohencu-ll.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 260777f6a7be1f16cc330a008300c11ebdea8f1cf9d8e96a0325274fd8fd5b2a --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 23:51:45,257 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 23:51:45,346 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-06 23:51:45,353 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 23:51:45,353 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 23:51:45,377 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 23:51:45,380 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 23:51:45,380 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 23:51:45,381 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 23:51:45,381 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 23:51:45,381 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 23:51:45,381 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 23:51:45,382 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 23:51:45,382 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 23:51:45,382 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 23:51:45,382 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 23:51:45,382 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 23:51:45,382 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 23:51:45,382 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 23:51:45,383 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 23:51:45,384 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 23:51:45,384 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 23:51:45,384 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 23:51:45,385 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 23:51:45,385 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 23:51:45,385 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 23:51:45,385 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 23:51:45,385 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 23:51:45,385 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 -> 260777f6a7be1f16cc330a008300c11ebdea8f1cf9d8e96a0325274fd8fd5b2a [2024-11-06 23:51:45,611 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 23:51:45,621 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 23:51:45,625 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 23:51:45,626 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 23:51:45,627 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 23:51:45,628 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c [2024-11-06 23:51:46,880 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 23:51:47,111 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 23:51:47,112 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_cohencu-ll.c [2024-11-06 23:51:47,117 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/12a9617d1/1aa97f9faf6d4de2b6cc9ec63a6d5a57/FLAGf8c94adbe [2024-11-06 23:51:47,448 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/12a9617d1/1aa97f9faf6d4de2b6cc9ec63a6d5a57 [2024-11-06 23:51:47,450 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 23:51:47,451 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 23:51:47,452 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 23:51:47,452 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 23:51:47,456 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 23:51:47,456 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,459 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4c28c74b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47, skipping insertion in model container [2024-11-06 23:51:47,459 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,475 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 23:51:47,560 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/recursified_nla-digbench/recursified_cohencu-ll.c[1124,1137] [2024-11-06 23:51:47,573 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 23:51:47,580 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 23:51:47,587 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/recursified_nla-digbench/recursified_cohencu-ll.c[1124,1137] [2024-11-06 23:51:47,596 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 23:51:47,605 INFO L204 MainTranslator]: Completed translation [2024-11-06 23:51:47,605 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47 WrapperNode [2024-11-06 23:51:47,605 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 23:51:47,606 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 23:51:47,606 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 23:51:47,606 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 23:51:47,610 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,615 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,626 INFO L138 Inliner]: procedures = 16, calls = 99, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 106 [2024-11-06 23:51:47,627 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 23:51:47,627 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 23:51:47,627 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 23:51:47,627 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 23:51:47,633 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,633 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,635 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,644 INFO L175 MemorySlicer]: Split 66 memory accesses to 6 slices as follows [2, 15, 21, 12, 5, 11]. 32 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 9 writes are split as follows [0, 2, 2, 2, 1, 2]. [2024-11-06 23:51:47,644 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,644 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,649 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,650 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,651 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,651 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,653 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 23:51:47,653 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 23:51:47,654 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 23:51:47,654 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 23:51:47,654 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (1/1) ... [2024-11-06 23:51:47,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 23:51:47,670 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:51:47,680 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 23:51:47,684 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 23:51:47,703 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-06 23:51:47,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_41_0 [2024-11-06 23:51:47,705 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_41_0 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 23:51:47,705 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-06 23:51:47,705 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 23:51:47,705 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 23:51:47,706 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-06 23:51:47,777 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 23:51:47,778 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 23:51:47,905 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-11-06 23:51:47,905 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 23:51:47,911 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 23:51:47,911 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-06 23:51:47,912 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 11:51:47 BoogieIcfgContainer [2024-11-06 23:51:47,913 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 23:51:47,914 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 23:51:47,914 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 23:51:47,918 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 23:51:47,918 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 11:51:47" (1/3) ... [2024-11-06 23:51:47,918 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61cedcb0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 11:51:47, skipping insertion in model container [2024-11-06 23:51:47,918 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 11:51:47" (2/3) ... [2024-11-06 23:51:47,919 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61cedcb0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 11:51:47, skipping insertion in model container [2024-11-06 23:51:47,920 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 11:51:47" (3/3) ... [2024-11-06 23:51:47,920 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_cohencu-ll.c [2024-11-06 23:51:47,933 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 23:51:47,933 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 23:51:47,967 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 23:51:47,974 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;@72ef2103, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 23:51:47,974 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 23:51:47,977 INFO L276 IsEmpty]: Start isEmpty. Operand has 41 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 26 states have internal predecessors, (28), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-06 23:51:47,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-06 23:51:47,981 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:51:47,981 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:51:47,981 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:51:47,984 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:51:47,984 INFO L85 PathProgramCache]: Analyzing trace with hash 252415097, now seen corresponding path program 1 times [2024-11-06 23:51:47,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:51:47,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776780353] [2024-11-06 23:51:47,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:47,989 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:51:48,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:51:48,532 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-06 23:51:48,532 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:51:48,532 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776780353] [2024-11-06 23:51:48,533 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [776780353] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 23:51:48,533 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 23:51:48,533 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-06 23:51:48,534 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1398859622] [2024-11-06 23:51:48,534 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 23:51:48,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 23:51:48,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:51:48,548 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 23:51:48,548 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-11-06 23:51:48,549 INFO L87 Difference]: Start difference. First operand has 41 states, 24 states have (on average 1.1666666666666667) internal successors, (28), 26 states have internal predecessors, (28), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-06 23:51:48,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:51:48,734 INFO L93 Difference]: Finished difference Result 99 states and 149 transitions. [2024-11-06 23:51:48,735 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 23:51:48,736 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-06 23:51:48,736 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:51:48,740 INFO L225 Difference]: With dead ends: 99 [2024-11-06 23:51:48,740 INFO L226 Difference]: Without dead ends: 57 [2024-11-06 23:51:48,742 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-06 23:51:48,744 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 23:51:48,744 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 222 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 140 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 23:51:48,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-06 23:51:48,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2024-11-06 23:51:48,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.0909090909090908) internal successors, (36), 35 states have internal predecessors, (36), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2024-11-06 23:51:48,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 72 transitions. [2024-11-06 23:51:48,777 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 72 transitions. Word has length 9 [2024-11-06 23:51:48,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:51:48,777 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 72 transitions. [2024-11-06 23:51:48,779 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-06 23:51:48,779 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 72 transitions. [2024-11-06 23:51:48,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-06 23:51:48,780 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:51:48,780 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:51:48,780 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-06 23:51:48,780 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:51:48,781 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:51:48,781 INFO L85 PathProgramCache]: Analyzing trace with hash -1306217988, now seen corresponding path program 1 times [2024-11-06 23:51:48,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:51:48,781 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1033205323] [2024-11-06 23:51:48,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:48,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:51:48,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:51:48,820 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1726875096] [2024-11-06 23:51:48,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:48,821 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:48,821 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:51:48,825 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 23:51:48,829 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 23:51:48,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:51:48,917 INFO L255 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-11-06 23:51:48,921 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:51:48,949 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:48,953 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:49,170 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-06 23:51:49,170 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:51:49,373 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:51:49,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1033205323] [2024-11-06 23:51:49,374 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:51:49,374 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1726875096] [2024-11-06 23:51:49,374 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1726875096] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:51:49,374 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:51:49,374 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-11-06 23:51:49,375 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1486237153] [2024-11-06 23:51:49,375 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 23:51:49,376 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-06 23:51:49,376 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:51:49,379 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-06 23:51:49,379 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=197, Unknown=0, NotChecked=0, Total=240 [2024-11-06 23:51:49,379 INFO L87 Difference]: Start difference. First operand 56 states and 72 transitions. Second operand has 13 states, 10 states have (on average 1.1) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 23:51:49,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:51:49,854 INFO L93 Difference]: Finished difference Result 80 states and 99 transitions. [2024-11-06 23:51:49,854 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-06 23:51:49,854 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 1.1) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-06 23:51:49,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:51:49,855 INFO L225 Difference]: With dead ends: 80 [2024-11-06 23:51:49,856 INFO L226 Difference]: Without dead ends: 78 [2024-11-06 23:51:49,857 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 4 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=102, Invalid=404, Unknown=0, NotChecked=0, Total=506 [2024-11-06 23:51:49,857 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 37 mSDsluCounter, 176 mSDsCounter, 0 mSdLazyCounter, 399 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 425 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 399 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 23:51:49,857 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 198 Invalid, 425 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 399 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 23:51:49,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-11-06 23:51:49,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 76. [2024-11-06 23:51:49,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 45 states have (on average 1.0888888888888888) internal successors, (49), 47 states have internal predecessors, (49), 24 states have call successors, (24), 6 states have call predecessors, (24), 6 states have return successors, (23), 23 states have call predecessors, (23), 22 states have call successors, (23) [2024-11-06 23:51:49,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 96 transitions. [2024-11-06 23:51:49,880 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 96 transitions. Word has length 15 [2024-11-06 23:51:49,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:51:49,880 INFO L471 AbstractCegarLoop]: Abstraction has 76 states and 96 transitions. [2024-11-06 23:51:49,880 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 1.1) internal successors, (11), 9 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 23:51:49,881 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 96 transitions. [2024-11-06 23:51:49,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-06 23:51:49,881 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:51:49,881 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:51:49,895 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-06 23:51:50,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:50,082 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:51:50,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:51:50,083 INFO L85 PathProgramCache]: Analyzing trace with hash 979710525, now seen corresponding path program 1 times [2024-11-06 23:51:50,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:51:50,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [743481275] [2024-11-06 23:51:50,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:50,083 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:51:50,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:51:50,108 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [532222395] [2024-11-06 23:51:50,108 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:50,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:50,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:51:50,111 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 23:51:50,112 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 23:51:50,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:51:50,178 INFO L255 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-06 23:51:50,180 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:51:50,183 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:50,187 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:50,335 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 23:51:50,335 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:51:50,404 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 23:51:50,405 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:51:50,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [743481275] [2024-11-06 23:51:50,406 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:51:50,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [532222395] [2024-11-06 23:51:50,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [532222395] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-06 23:51:50,406 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:51:50,406 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 9 [2024-11-06 23:51:50,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1052442558] [2024-11-06 23:51:50,406 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 23:51:50,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 23:51:50,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:51:50,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 23:51:50,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2024-11-06 23:51:50,407 INFO L87 Difference]: Start difference. First operand 76 states and 96 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 23:51:50,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:51:50,531 INFO L93 Difference]: Finished difference Result 82 states and 101 transitions. [2024-11-06 23:51:50,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 23:51:50,531 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2024-11-06 23:51:50,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:51:50,532 INFO L225 Difference]: With dead ends: 82 [2024-11-06 23:51:50,532 INFO L226 Difference]: Without dead ends: 80 [2024-11-06 23:51:50,532 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 27 SyntacticMatches, 6 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2024-11-06 23:51:50,533 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 18 mSDsluCounter, 186 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 23:51:50,533 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 225 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 23:51:50,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2024-11-06 23:51:50,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 80. [2024-11-06 23:51:50,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 48 states have (on average 1.0833333333333333) internal successors, (52), 50 states have internal predecessors, (52), 24 states have call successors, (24), 7 states have call predecessors, (24), 7 states have return successors, (23), 23 states have call predecessors, (23), 22 states have call successors, (23) [2024-11-06 23:51:50,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 99 transitions. [2024-11-06 23:51:50,542 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 99 transitions. Word has length 21 [2024-11-06 23:51:50,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:51:50,542 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 99 transitions. [2024-11-06 23:51:50,542 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 23:51:50,542 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 99 transitions. [2024-11-06 23:51:50,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-06 23:51:50,543 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:51:50,543 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:51:50,557 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 23:51:50,746 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:50,746 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:51:50,747 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:51:50,747 INFO L85 PathProgramCache]: Analyzing trace with hash 574719676, now seen corresponding path program 1 times [2024-11-06 23:51:50,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:51:50,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1309263922] [2024-11-06 23:51:50,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:50,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:51:50,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:51:50,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1542797908] [2024-11-06 23:51:50,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:50,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:50,787 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:51:50,790 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 23:51:50,794 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 23:51:50,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:51:50,867 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 76 conjuncts are in the unsatisfiable core [2024-11-06 23:51:50,869 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:51:50,878 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:50,883 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:50,888 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:50,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:51,286 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-06 23:51:51,286 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:51:51,897 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-06 23:51:51,897 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:51:51,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1309263922] [2024-11-06 23:51:51,897 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:51:51,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1542797908] [2024-11-06 23:51:51,897 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1542797908] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 23:51:51,897 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 23:51:51,898 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 21 [2024-11-06 23:51:51,898 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [235710889] [2024-11-06 23:51:51,898 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 23:51:51,898 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-06 23:51:51,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:51:51,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-06 23:51:51,898 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-06 23:51:51,899 INFO L87 Difference]: Start difference. First operand 80 states and 99 transitions. Second operand has 21 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 18 states have internal predecessors, (28), 8 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-06 23:51:58,035 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2024-11-06 23:51:58,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:51:58,468 INFO L93 Difference]: Finished difference Result 110 states and 134 transitions. [2024-11-06 23:51:58,469 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-06 23:51:58,470 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 18 states have internal predecessors, (28), 8 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) Word has length 27 [2024-11-06 23:51:58,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:51:58,474 INFO L225 Difference]: With dead ends: 110 [2024-11-06 23:51:58,475 INFO L226 Difference]: Without dead ends: 108 [2024-11-06 23:51:58,476 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 30 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=170, Invalid=822, Unknown=0, NotChecked=0, Total=992 [2024-11-06 23:51:58,477 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 70 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 488 mSolverCounterSat, 55 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 544 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 488 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.8s IncrementalHoareTripleChecker+Time [2024-11-06 23:51:58,478 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 114 Invalid, 544 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 488 Invalid, 1 Unknown, 0 Unchecked, 5.8s Time] [2024-11-06 23:51:58,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2024-11-06 23:51:58,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 106. [2024-11-06 23:51:58,510 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 64 states have (on average 1.078125) internal successors, (69), 67 states have internal predecessors, (69), 30 states have call successors, (30), 10 states have call predecessors, (30), 11 states have return successors, (31), 29 states have call predecessors, (31), 28 states have call successors, (31) [2024-11-06 23:51:58,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 130 transitions. [2024-11-06 23:51:58,513 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 130 transitions. Word has length 27 [2024-11-06 23:51:58,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:51:58,513 INFO L471 AbstractCegarLoop]: Abstraction has 106 states and 130 transitions. [2024-11-06 23:51:58,513 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 18 states have internal predecessors, (28), 8 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (6), 2 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-06 23:51:58,513 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 130 transitions. [2024-11-06 23:51:58,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-06 23:51:58,514 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:51:58,514 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:51:58,535 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 23:51:58,714 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:58,714 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:51:58,715 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:51:58,715 INFO L85 PathProgramCache]: Analyzing trace with hash -2108880647, now seen corresponding path program 1 times [2024-11-06 23:51:58,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:51:58,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1048132841] [2024-11-06 23:51:58,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:58,716 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:51:58,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:51:58,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [883777619] [2024-11-06 23:51:58,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:51:58,749 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:51:58,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:51:58,751 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 23:51:58,752 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 23:51:58,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:51:58,846 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-06 23:51:58,848 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:51:58,863 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:51:58,884 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:01,110 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 3 proven. 17 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-06 23:52:01,111 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:52:02,463 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 30 [2024-11-06 23:52:02,957 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-06 23:52:02,957 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:52:02,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1048132841] [2024-11-06 23:52:02,957 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:52:02,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [883777619] [2024-11-06 23:52:02,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [883777619] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 23:52:02,957 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 23:52:02,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 22 [2024-11-06 23:52:02,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1729278218] [2024-11-06 23:52:02,957 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 23:52:02,957 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-06 23:52:02,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:52:02,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-06 23:52:02,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2024-11-06 23:52:02,958 INFO L87 Difference]: Start difference. First operand 106 states and 130 transitions. Second operand has 22 states, 16 states have (on average 1.875) internal successors, (30), 18 states have internal predecessors, (30), 8 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (8), 2 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-06 23:52:12,785 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2024-11-06 23:52:12,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:52:12,954 INFO L93 Difference]: Finished difference Result 119 states and 142 transitions. [2024-11-06 23:52:12,956 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-06 23:52:12,956 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 16 states have (on average 1.875) internal successors, (30), 18 states have internal predecessors, (30), 8 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (8), 2 states have call predecessors, (8), 4 states have call successors, (8) Word has length 33 [2024-11-06 23:52:12,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:52:12,958 INFO L225 Difference]: With dead ends: 119 [2024-11-06 23:52:12,958 INFO L226 Difference]: Without dead ends: 117 [2024-11-06 23:52:12,961 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 38 SyntacticMatches, 7 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 259 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=235, Invalid=1247, Unknown=0, NotChecked=0, Total=1482 [2024-11-06 23:52:12,962 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 92 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 466 mSolverCounterSat, 60 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 527 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 466 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.4s IncrementalHoareTripleChecker+Time [2024-11-06 23:52:12,962 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [97 Valid, 147 Invalid, 527 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 466 Invalid, 1 Unknown, 0 Unchecked, 7.4s Time] [2024-11-06 23:52:12,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-06 23:52:12,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 114. [2024-11-06 23:52:12,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 70 states have (on average 1.0714285714285714) internal successors, (75), 73 states have internal predecessors, (75), 30 states have call successors, (30), 12 states have call predecessors, (30), 13 states have return successors, (31), 29 states have call predecessors, (31), 28 states have call successors, (31) [2024-11-06 23:52:12,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 136 transitions. [2024-11-06 23:52:12,999 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 136 transitions. Word has length 33 [2024-11-06 23:52:12,999 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:52:12,999 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 136 transitions. [2024-11-06 23:52:13,000 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 16 states have (on average 1.875) internal successors, (30), 18 states have internal predecessors, (30), 8 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (8), 2 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-06 23:52:13,000 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 136 transitions. [2024-11-06 23:52:13,005 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-06 23:52:13,005 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:52:13,005 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 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 23:52:13,018 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-06 23:52:13,206 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 23:52:13,206 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:52:13,206 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:52:13,206 INFO L85 PathProgramCache]: Analyzing trace with hash -1839768368, now seen corresponding path program 1 times [2024-11-06 23:52:13,206 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:52:13,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1049647245] [2024-11-06 23:52:13,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:13,206 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:52:13,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-06 23:52:14,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,428 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-06 23:52:14,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-06 23:52:14,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,435 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-06 23:52:14,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-06 23:52:14,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,446 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-06 23:52:14,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:52:14,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1049647245] [2024-11-06 23:52:14,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1049647245] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:52:14,447 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1887770950] [2024-11-06 23:52:14,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:14,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:52:14,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:52:14,449 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 23:52:14,450 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 23:52:14,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:14,539 INFO L255 TraceCheckSpWp]: Trace formula consists of 306 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-06 23:52:14,545 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:52:16,222 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-11-06 23:52:16,233 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-11-06 23:52:16,376 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2024-11-06 23:52:16,386 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-06 23:52:16,828 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 7 proven. 22 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 23:52:16,828 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:52:22,101 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 11 proven. 14 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-06 23:52:22,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1887770950] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 23:52:22,101 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 23:52:22,101 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 10] total 21 [2024-11-06 23:52:22,101 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1823931297] [2024-11-06 23:52:22,101 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 23:52:22,102 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-06 23:52:22,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:52:22,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-06 23:52:22,102 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=356, Unknown=1, NotChecked=0, Total=420 [2024-11-06 23:52:22,103 INFO L87 Difference]: Start difference. First operand 114 states and 136 transitions. Second operand has 21 states, 16 states have (on average 2.5625) internal successors, (41), 17 states have internal predecessors, (41), 9 states have call successors, (21), 7 states have call predecessors, (21), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-06 23:52:27,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:52:27,035 INFO L93 Difference]: Finished difference Result 124 states and 146 transitions. [2024-11-06 23:52:27,035 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-06 23:52:27,035 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.5625) internal successors, (41), 17 states have internal predecessors, (41), 9 states have call successors, (21), 7 states have call predecessors, (21), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) Word has length 43 [2024-11-06 23:52:27,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:52:27,036 INFO L225 Difference]: With dead ends: 124 [2024-11-06 23:52:27,036 INFO L226 Difference]: Without dead ends: 122 [2024-11-06 23:52:27,037 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 80 SyntacticMatches, 9 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=155, Invalid=774, Unknown=1, NotChecked=0, Total=930 [2024-11-06 23:52:27,037 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 77 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 691 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 732 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 691 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.7s IncrementalHoareTripleChecker+Time [2024-11-06 23:52:27,037 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 171 Invalid, 732 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 691 Invalid, 0 Unknown, 0 Unchecked, 3.7s Time] [2024-11-06 23:52:27,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-06 23:52:27,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 122. [2024-11-06 23:52:27,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 75 states have (on average 1.0666666666666667) internal successors, (80), 78 states have internal predecessors, (80), 30 states have call successors, (30), 13 states have call predecessors, (30), 16 states have return successors, (34), 30 states have call predecessors, (34), 28 states have call successors, (34) [2024-11-06 23:52:27,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 144 transitions. [2024-11-06 23:52:27,067 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 144 transitions. Word has length 43 [2024-11-06 23:52:27,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:52:27,071 INFO L471 AbstractCegarLoop]: Abstraction has 122 states and 144 transitions. [2024-11-06 23:52:27,071 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.5625) internal successors, (41), 17 states have internal predecessors, (41), 9 states have call successors, (21), 7 states have call predecessors, (21), 4 states have return successors, (15), 2 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-06 23:52:27,071 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 144 transitions. [2024-11-06 23:52:27,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-06 23:52:27,072 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:52:27,072 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 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, 1, 1] [2024-11-06 23:52:27,088 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 23:52:27,272 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 23:52:27,273 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:52:27,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:52:27,273 INFO L85 PathProgramCache]: Analyzing trace with hash -262292946, now seen corresponding path program 1 times [2024-11-06 23:52:27,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:52:27,273 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1960601619] [2024-11-06 23:52:27,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:27,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:52:27,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,773 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 23:52:27,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,935 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 23:52:27,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,938 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-06 23:52:27,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,940 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-06 23:52:27,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,942 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-06 23:52:27,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,945 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-06 23:52:27,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:27,947 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-06 23:52:27,947 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:52:27,948 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1960601619] [2024-11-06 23:52:27,948 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1960601619] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 23:52:27,948 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 23:52:27,948 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-06 23:52:27,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1367965007] [2024-11-06 23:52:27,948 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 23:52:27,948 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 23:52:27,948 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:52:27,949 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 23:52:27,949 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-06 23:52:27,949 INFO L87 Difference]: Start difference. First operand 122 states and 144 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-06 23:52:29,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:52:29,080 INFO L93 Difference]: Finished difference Result 128 states and 149 transitions. [2024-11-06 23:52:29,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-06 23:52:29,080 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 43 [2024-11-06 23:52:29,080 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:52:29,082 INFO L225 Difference]: With dead ends: 128 [2024-11-06 23:52:29,082 INFO L226 Difference]: Without dead ends: 126 [2024-11-06 23:52:29,082 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2024-11-06 23:52:29,083 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 22 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 193 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-06 23:52:29,083 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 100 Invalid, 193 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-06 23:52:29,085 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-06 23:52:29,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 126. [2024-11-06 23:52:29,129 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 78 states have (on average 1.064102564102564) internal successors, (83), 81 states have internal predecessors, (83), 30 states have call successors, (30), 14 states have call predecessors, (30), 17 states have return successors, (34), 30 states have call predecessors, (34), 28 states have call successors, (34) [2024-11-06 23:52:29,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 147 transitions. [2024-11-06 23:52:29,130 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 147 transitions. Word has length 43 [2024-11-06 23:52:29,130 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:52:29,130 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 147 transitions. [2024-11-06 23:52:29,130 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-06 23:52:29,130 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 147 transitions. [2024-11-06 23:52:29,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-06 23:52:29,135 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:52:29,136 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:52:29,136 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-06 23:52:29,136 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:52:29,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:52:29,136 INFO L85 PathProgramCache]: Analyzing trace with hash 1536337171, now seen corresponding path program 2 times [2024-11-06 23:52:29,136 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:52:29,136 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1253835504] [2024-11-06 23:52:29,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:29,136 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:52:29,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:52:29,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [989916110] [2024-11-06 23:52:29,165 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-06 23:52:29,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:52:29,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:52:29,167 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 23:52:29,168 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 23:52:29,271 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-06 23:52:29,272 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 23:52:29,275 INFO L255 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 92 conjuncts are in the unsatisfiable core [2024-11-06 23:52:29,278 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:52:29,298 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:29,323 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:29,350 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:31,734 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-06 23:52:31,765 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-06 23:52:31,800 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-06 23:52:32,993 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-06 23:52:32,993 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:52:35,595 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 13 proven. 19 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-06 23:52:35,595 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:52:35,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1253835504] [2024-11-06 23:52:35,595 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:52:35,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [989916110] [2024-11-06 23:52:35,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [989916110] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 23:52:35,595 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 23:52:35,595 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 25 [2024-11-06 23:52:35,595 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [782733456] [2024-11-06 23:52:35,595 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 23:52:35,596 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-06 23:52:35,596 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:52:35,596 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-06 23:52:35,596 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=518, Unknown=0, NotChecked=0, Total=600 [2024-11-06 23:52:35,596 INFO L87 Difference]: Start difference. First operand 126 states and 147 transitions. Second operand has 25 states, 19 states have (on average 2.263157894736842) internal successors, (43), 20 states have internal predecessors, (43), 10 states have call successors, (18), 8 states have call predecessors, (18), 5 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-06 23:52:45,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:52:45,764 INFO L93 Difference]: Finished difference Result 160 states and 182 transitions. [2024-11-06 23:52:45,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2024-11-06 23:52:45,764 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 19 states have (on average 2.263157894736842) internal successors, (43), 20 states have internal predecessors, (43), 10 states have call successors, (18), 8 states have call predecessors, (18), 5 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) Word has length 49 [2024-11-06 23:52:45,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:52:45,765 INFO L225 Difference]: With dead ends: 160 [2024-11-06 23:52:45,767 INFO L226 Difference]: Without dead ends: 158 [2024-11-06 23:52:45,768 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 61 SyntacticMatches, 12 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 423 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=308, Invalid=1762, Unknown=0, NotChecked=0, Total=2070 [2024-11-06 23:52:45,768 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 113 mSDsluCounter, 244 mSDsCounter, 0 mSdLazyCounter, 1198 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 118 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 1265 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 1198 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.2s IncrementalHoareTripleChecker+Time [2024-11-06 23:52:45,769 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [118 Valid, 282 Invalid, 1265 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 1198 Invalid, 0 Unknown, 0 Unchecked, 7.2s Time] [2024-11-06 23:52:45,769 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-11-06 23:52:45,801 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 154. [2024-11-06 23:52:45,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 96 states have (on average 1.0625) internal successors, (102), 99 states have internal predecessors, (102), 36 states have call successors, (36), 18 states have call predecessors, (36), 21 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-11-06 23:52:45,806 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 177 transitions. [2024-11-06 23:52:45,806 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 177 transitions. Word has length 49 [2024-11-06 23:52:45,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:52:45,806 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 177 transitions. [2024-11-06 23:52:45,807 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 19 states have (on average 2.263157894736842) internal successors, (43), 20 states have internal predecessors, (43), 10 states have call successors, (18), 8 states have call predecessors, (18), 5 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-06 23:52:45,807 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 177 transitions. [2024-11-06 23:52:45,807 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-06 23:52:45,807 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:52:45,807 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 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, 1, 1, 1, 1, 1] [2024-11-06 23:52:45,821 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 23:52:46,007 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,SelfDestructingSolverStorable7 [2024-11-06 23:52:46,008 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:52:46,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:52:46,008 INFO L85 PathProgramCache]: Analyzing trace with hash -966431251, now seen corresponding path program 1 times [2024-11-06 23:52:46,008 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:52:46,009 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1853589063] [2024-11-06 23:52:46,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:46,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:52:46,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:52:46,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1304862947] [2024-11-06 23:52:46,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:46,040 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:52:46,040 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:52:46,042 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 23:52:46,043 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 23:52:46,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:52:46,128 INFO L255 TraceCheckSpWp]: Trace formula consists of 263 conjuncts, 55 conjuncts are in the unsatisfiable core [2024-11-06 23:52:46,130 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:52:46,155 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:46,178 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 35 [2024-11-06 23:52:46,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-06 23:52:46,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-06 23:52:46,281 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:46,302 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-06 23:52:50,355 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-06 23:52:50,387 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 23 [2024-11-06 23:52:50,739 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 20 proven. 12 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-06 23:52:50,739 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:52:55,411 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:52:55,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1853589063] [2024-11-06 23:52:55,412 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:52:55,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1304862947] [2024-11-06 23:52:55,412 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1304862947] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:52:55,412 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:52:55,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2024-11-06 23:52:55,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2017811530] [2024-11-06 23:52:55,412 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 23:52:55,412 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-06 23:52:55,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:52:55,412 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-06 23:52:55,412 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=120, Unknown=1, NotChecked=0, Total=156 [2024-11-06 23:52:55,413 INFO L87 Difference]: Start difference. First operand 154 states and 177 transitions. Second operand has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-06 23:52:58,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:52:58,824 INFO L93 Difference]: Finished difference Result 162 states and 183 transitions. [2024-11-06 23:52:58,824 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-06 23:52:58,824 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 49 [2024-11-06 23:52:58,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:52:58,826 INFO L225 Difference]: With dead ends: 162 [2024-11-06 23:52:58,826 INFO L226 Difference]: Without dead ends: 160 [2024-11-06 23:52:58,827 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 39 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=71, Invalid=234, Unknown=1, NotChecked=0, Total=306 [2024-11-06 23:52:58,828 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 51 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 300 mSolverCounterSat, 38 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 74 SdHoareTripleChecker+Invalid, 340 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 300 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-06 23:52:58,829 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 74 Invalid, 340 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 300 Invalid, 2 Unknown, 0 Unchecked, 2.2s Time] [2024-11-06 23:52:58,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2024-11-06 23:52:58,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 158. [2024-11-06 23:52:58,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 99 states have (on average 1.0606060606060606) internal successors, (105), 102 states have internal predecessors, (105), 36 states have call successors, (36), 19 states have call predecessors, (36), 22 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-11-06 23:52:58,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 180 transitions. [2024-11-06 23:52:58,858 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 180 transitions. Word has length 49 [2024-11-06 23:52:58,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:52:58,858 INFO L471 AbstractCegarLoop]: Abstraction has 158 states and 180 transitions. [2024-11-06 23:52:58,858 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.2) internal successors, (22), 10 states have internal predecessors, (22), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-06 23:52:58,858 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 180 transitions. [2024-11-06 23:52:58,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-06 23:52:58,859 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:52:58,859 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:52:58,873 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-06 23:52:59,062 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:52:59,062 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:52:59,063 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:52:59,063 INFO L85 PathProgramCache]: Analyzing trace with hash -1459603436, now seen corresponding path program 3 times [2024-11-06 23:52:59,063 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:52:59,063 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2060940432] [2024-11-06 23:52:59,063 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:52:59,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:52:59,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:52:59,092 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [982447109] [2024-11-06 23:52:59,092 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-06 23:52:59,092 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:52:59,092 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:52:59,095 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 23:52:59,101 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 23:52:59,188 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-06 23:52:59,189 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 23:52:59,190 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 86 conjuncts are in the unsatisfiable core [2024-11-06 23:52:59,193 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:52:59,233 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:59,271 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:52:59,297 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:01,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-06 23:53:01,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-06 23:53:03,315 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 61 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-06 23:53:03,315 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:53:04,825 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 14 proven. 7 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-06 23:53:04,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:53:04,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2060940432] [2024-11-06 23:53:04,829 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:53:04,829 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [982447109] [2024-11-06 23:53:04,829 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [982447109] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 23:53:04,829 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 23:53:04,829 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 20 [2024-11-06 23:53:04,829 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1123928976] [2024-11-06 23:53:04,829 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 23:53:04,830 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-06 23:53:04,830 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:53:04,830 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-06 23:53:04,830 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=328, Unknown=0, NotChecked=0, Total=380 [2024-11-06 23:53:04,830 INFO L87 Difference]: Start difference. First operand 158 states and 180 transitions. Second operand has 20 states, 16 states have (on average 2.5625) internal successors, (41), 14 states have internal predecessors, (41), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-06 23:53:09,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:53:09,533 INFO L93 Difference]: Finished difference Result 168 states and 187 transitions. [2024-11-06 23:53:09,533 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-06 23:53:09,533 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 16 states have (on average 2.5625) internal successors, (41), 14 states have internal predecessors, (41), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 55 [2024-11-06 23:53:09,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:53:09,534 INFO L225 Difference]: With dead ends: 168 [2024-11-06 23:53:09,534 INFO L226 Difference]: Without dead ends: 166 [2024-11-06 23:53:09,535 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 79 SyntacticMatches, 12 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=115, Invalid=641, Unknown=0, NotChecked=0, Total=756 [2024-11-06 23:53:09,535 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 117 mSDsluCounter, 260 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 117 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 664 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.4s IncrementalHoareTripleChecker+Time [2024-11-06 23:53:09,535 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [117 Valid, 316 Invalid, 664 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 622 Invalid, 0 Unknown, 0 Unchecked, 3.4s Time] [2024-11-06 23:53:09,536 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2024-11-06 23:53:09,569 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 162. [2024-11-06 23:53:09,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 162 states, 102 states have (on average 1.0588235294117647) internal successors, (108), 105 states have internal predecessors, (108), 36 states have call successors, (36), 20 states have call predecessors, (36), 23 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-11-06 23:53:09,571 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 183 transitions. [2024-11-06 23:53:09,572 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 183 transitions. Word has length 55 [2024-11-06 23:53:09,572 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:53:09,572 INFO L471 AbstractCegarLoop]: Abstraction has 162 states and 183 transitions. [2024-11-06 23:53:09,572 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 16 states have (on average 2.5625) internal successors, (41), 14 states have internal predecessors, (41), 8 states have call successors, (20), 9 states have call predecessors, (20), 3 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2024-11-06 23:53:09,572 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 183 transitions. [2024-11-06 23:53:09,573 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-06 23:53:09,575 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:53:09,575 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:53:09,589 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-06 23:53:09,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:53:09,779 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:53:09,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:53:09,779 INFO L85 PathProgramCache]: Analyzing trace with hash 837279594, now seen corresponding path program 1 times [2024-11-06 23:53:09,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:53:09,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069539730] [2024-11-06 23:53:09,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:09,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:53:09,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:53:09,801 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [4889326] [2024-11-06 23:53:09,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:09,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:53:09,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:53:09,806 INFO L229 MonitoredProcess]: Starting monitored process 10 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 23:53:09,813 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-06 23:53:09,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:53:09,903 INFO L255 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-06 23:53:09,906 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:53:09,921 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:09,954 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-06 23:53:09,965 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 35 [2024-11-06 23:53:09,988 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-06 23:53:10,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-06 23:53:10,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:13,490 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-11-06 23:53:15,379 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 23:53:15,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 68 treesize of output 72 [2024-11-06 23:53:15,840 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 40 proven. 14 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-06 23:53:15,840 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:53:18,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:53:18,389 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069539730] [2024-11-06 23:53:18,389 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:53:18,389 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [4889326] [2024-11-06 23:53:18,389 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [4889326] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:53:18,389 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:53:18,389 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-11-06 23:53:18,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [176725825] [2024-11-06 23:53:18,390 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 23:53:18,390 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-06 23:53:18,390 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:53:18,391 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-06 23:53:18,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=283, Unknown=0, NotChecked=0, Total=342 [2024-11-06 23:53:18,391 INFO L87 Difference]: Start difference. First operand 162 states and 183 transitions. Second operand has 13 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-06 23:53:22,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:53:22,260 INFO L93 Difference]: Finished difference Result 170 states and 189 transitions. [2024-11-06 23:53:22,261 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-06 23:53:22,261 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) Word has length 55 [2024-11-06 23:53:22,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:53:22,262 INFO L225 Difference]: With dead ends: 170 [2024-11-06 23:53:22,262 INFO L226 Difference]: Without dead ends: 168 [2024-11-06 23:53:22,263 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 55 SyntacticMatches, 5 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 139 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=111, Invalid=539, Unknown=0, NotChecked=0, Total=650 [2024-11-06 23:53:22,263 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 36 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 411 mSolverCounterSat, 25 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 438 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 411 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2024-11-06 23:53:22,263 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 68 Invalid, 438 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 411 Invalid, 2 Unknown, 0 Unchecked, 2.4s Time] [2024-11-06 23:53:22,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2024-11-06 23:53:22,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 166. [2024-11-06 23:53:22,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 105 states have (on average 1.0571428571428572) internal successors, (111), 108 states have internal predecessors, (111), 36 states have call successors, (36), 21 states have call predecessors, (36), 24 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-11-06 23:53:22,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 186 transitions. [2024-11-06 23:53:22,314 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 186 transitions. Word has length 55 [2024-11-06 23:53:22,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:53:22,314 INFO L471 AbstractCegarLoop]: Abstraction has 166 states and 186 transitions. [2024-11-06 23:53:22,314 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (8), 2 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-06 23:53:22,314 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 186 transitions. [2024-11-06 23:53:22,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-06 23:53:22,316 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:53:22,316 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:53:22,330 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-06 23:53:22,516 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:53:22,517 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:53:22,517 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:53:22,517 INFO L85 PathProgramCache]: Analyzing trace with hash -335329243, now seen corresponding path program 1 times [2024-11-06 23:53:22,517 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:53:22,517 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2123033345] [2024-11-06 23:53:22,517 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:22,517 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:53:22,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:53:22,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1169844543] [2024-11-06 23:53:22,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:22,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:53:22,535 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:53:22,541 INFO L229 MonitoredProcess]: Starting monitored process 11 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 23:53:22,542 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-06 23:53:22,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:53:22,643 INFO L255 TraceCheckSpWp]: Trace formula consists of 305 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-06 23:53:22,645 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:53:22,668 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:22,690 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:22,714 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:24,572 INFO L134 CoverageAnalysis]: Checked inductivity of 128 backedges. 70 proven. 6 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-06 23:53:24,572 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:53:26,220 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:53:26,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2123033345] [2024-11-06 23:53:26,220 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:53:26,220 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1169844543] [2024-11-06 23:53:26,220 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1169844543] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:53:26,220 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:53:26,220 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-11-06 23:53:26,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1389819375] [2024-11-06 23:53:26,220 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 23:53:26,220 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 23:53:26,221 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:53:26,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 23:53:26,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2024-11-06 23:53:26,221 INFO L87 Difference]: Start difference. First operand 166 states and 186 transitions. Second operand has 8 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 7 states have internal predecessors, (24), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-06 23:53:27,948 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 23:53:27,948 INFO L93 Difference]: Finished difference Result 174 states and 192 transitions. [2024-11-06 23:53:27,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-06 23:53:27,948 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 7 states have internal predecessors, (24), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 61 [2024-11-06 23:53:27,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 23:53:27,949 INFO L225 Difference]: With dead ends: 174 [2024-11-06 23:53:27,950 INFO L226 Difference]: Without dead ends: 172 [2024-11-06 23:53:27,950 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 75 SyntacticMatches, 7 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2024-11-06 23:53:27,950 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 30 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 210 mSolverCounterSat, 40 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 251 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 210 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-06 23:53:27,950 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 87 Invalid, 251 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 210 Invalid, 1 Unknown, 0 Unchecked, 1.2s Time] [2024-11-06 23:53:27,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2024-11-06 23:53:27,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 170. [2024-11-06 23:53:27,992 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 108 states have (on average 1.0555555555555556) internal successors, (114), 111 states have internal predecessors, (114), 36 states have call successors, (36), 22 states have call predecessors, (36), 25 states have return successors, (39), 36 states have call predecessors, (39), 33 states have call successors, (39) [2024-11-06 23:53:27,993 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 189 transitions. [2024-11-06 23:53:27,993 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 189 transitions. Word has length 61 [2024-11-06 23:53:27,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 23:53:27,994 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 189 transitions. [2024-11-06 23:53:27,994 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.4285714285714284) internal successors, (24), 7 states have internal predecessors, (24), 3 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-06 23:53:27,994 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 189 transitions. [2024-11-06 23:53:27,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-06 23:53:27,994 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 23:53:27,994 INFO L215 NwaCegarLoop]: trace histogram [10, 9, 9, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 23:53:28,007 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-06 23:53:28,198 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-06 23:53:28,198 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 23:53:28,199 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 23:53:28,199 INFO L85 PathProgramCache]: Analyzing trace with hash -1784364642, now seen corresponding path program 1 times [2024-11-06 23:53:28,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 23:53:28,199 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1671995270] [2024-11-06 23:53:28,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:28,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 23:53:28,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 23:53:28,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1489588126] [2024-11-06 23:53:28,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 23:53:28,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 23:53:28,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 23:53:28,234 INFO L229 MonitoredProcess]: Starting monitored process 12 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 23:53:28,236 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-06 23:53:28,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 23:53:28,324 INFO L255 TraceCheckSpWp]: Trace formula consists of 322 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-06 23:53:28,326 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 23:53:28,341 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:28,365 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-06 23:53:29,860 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 90 proven. 8 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-06 23:53:29,860 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 23:53:30,812 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 23:53:30,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1671995270] [2024-11-06 23:53:30,813 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 23:53:30,813 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1489588126] [2024-11-06 23:53:30,813 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1489588126] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 23:53:30,813 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 23:53:30,813 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-11-06 23:53:30,813 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618427154] [2024-11-06 23:53:30,813 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 23:53:30,813 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 23:53:30,813 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 23:53:30,817 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 23:53:30,817 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2024-11-06 23:53:30,817 INFO L87 Difference]: Start difference. First operand 170 states and 189 transitions. Second operand has 8 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 7 states have internal predecessors, (25), 3 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10)