./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4f9af400 extending candidate: java ['java'] extending candidate: /usr/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/oracle-jdk-bin-*/bin/java ['java', '/usr/bin/java'] extending candidate: /opt/openjdk-*/bin/java ['java', '/usr/bin/java'] extending candidate: /usr/lib/jvm/java-*-openjdk-amd64/bin/java ['java', '/usr/bin/java', '/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java', '/usr/lib/jvm/java-17-openjdk-amd64/bin/java', '/usr/lib/jvm/java-11-openjdk-amd64/bin/java', '/usr/lib/jvm/java-1.17.0-openjdk-amd64/bin/java'] ['/root/.sdkman/candidates/java/21.0.5-tem/bin/java', '-Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config', '-Xmx15G', '-Xms4m', '-jar', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar', '-data', '@noDefault', '-ultimatedata', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data', '-tc', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml', '-i', '../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.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', 'aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3'] Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.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 aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 22:54:52,204 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 22:54:52,282 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-06 22:54:52,288 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 22:54:52,288 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 22:54:52,312 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 22:54:52,313 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 22:54:52,313 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 22:54:52,313 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 22:54:52,314 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 22:54:52,314 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 22:54:52,314 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 22:54:52,314 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 22:54:52,314 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 22:54:52,315 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 22:54:52,315 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 22:54:52,315 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 22:54:52,315 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 22:54:52,316 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 22:54:52,318 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:52,318 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 22:54:52,318 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 22:54:52,319 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 22:54:52,319 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 22:54:52,319 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 22:54:52,319 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 -> aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 [2024-11-06 22:54:52,597 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 22:54:52,607 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 22:54:52,609 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 22:54:52,610 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 22:54:52,610 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 22:54:52,613 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2024-11-06 22:54:53,853 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 22:54:54,098 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 22:54:54,101 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2024-11-06 22:54:54,108 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d50d4054b/c0f78fb484304956816a53ccf75a2827/FLAGfa1e8b7af [2024-11-06 22:54:54,435 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/d50d4054b/c0f78fb484304956816a53ccf75a2827 [2024-11-06 22:54:54,438 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 22:54:54,439 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 22:54:54,441 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:54,441 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 22:54:54,445 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 22:54:54,445 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,446 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@d454feb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54, skipping insertion in model container [2024-11-06 22:54:54,446 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,456 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 22:54:54,573 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c[490,503] [2024-11-06 22:54:54,597 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:54,605 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 22:54:54,616 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c[490,503] [2024-11-06 22:54:54,627 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:54:54,638 INFO L204 MainTranslator]: Completed translation [2024-11-06 22:54:54,640 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54 WrapperNode [2024-11-06 22:54:54,640 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 22:54:54,641 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:54,642 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 22:54:54,642 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 22:54:54,647 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,652 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,668 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2024-11-06 22:54:54,670 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 22:54:54,671 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 22:54:54,671 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 22:54:54,671 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 22:54:54,678 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,678 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,680 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,694 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-06 22:54:54,695 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,695 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,698 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,704 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,705 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,708 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,709 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 22:54:54,710 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 22:54:54,710 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 22:54:54,710 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 22:54:54,711 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (1/1) ... [2024-11-06 22:54:54,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:54:54,732 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:54,743 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-06 22:54:54,746 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-06 22:54:54,767 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 22:54:54,767 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-06 22:54:54,767 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-06 22:54:54,767 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 22:54:54,767 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 22:54:54,767 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 22:54:54,767 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 22:54:54,767 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 22:54:54,825 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 22:54:54,826 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 22:54:54,939 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-06 22:54:54,940 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 22:54:54,947 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 22:54:54,947 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-06 22:54:54,948 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:54 BoogieIcfgContainer [2024-11-06 22:54:54,948 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 22:54:54,950 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 22:54:54,950 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 22:54:54,953 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 22:54:54,954 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:54:54" (1/3) ... [2024-11-06 22:54:54,954 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7566cb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:54, skipping insertion in model container [2024-11-06 22:54:54,955 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:54:54" (2/3) ... [2024-11-06 22:54:54,955 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7566cb3 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:54:54, skipping insertion in model container [2024-11-06 22:54:54,955 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:54:54" (3/3) ... [2024-11-06 22:54:54,956 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound10.c [2024-11-06 22:54:54,968 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 22:54:54,969 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 22:54:55,003 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 22:54:55,013 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;@36f4bc5a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 22:54:55,014 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 22:54:55,019 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-06 22:54:55,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-06 22:54:55,027 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:55,028 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:55,028 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:55,032 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:55,032 INFO L85 PathProgramCache]: Analyzing trace with hash 1022199732, now seen corresponding path program 1 times [2024-11-06 22:54:55,039 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:55,040 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1784866032] [2024-11-06 22:54:55,040 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:55,041 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:55,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,154 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:55,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,163 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:55,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,167 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:55,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,173 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:55,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,183 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:55,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:55,184 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1784866032] [2024-11-06 22:54:55,185 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1784866032] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:55,185 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:55,186 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-06 22:54:55,187 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1268393480] [2024-11-06 22:54:55,188 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:55,190 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-06 22:54:55,190 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:55,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-06 22:54:55,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 22:54:55,208 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-06 22:54:55,227 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:55,228 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2024-11-06 22:54:55,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-06 22:54:55,229 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-06 22:54:55,229 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:55,234 INFO L225 Difference]: With dead ends: 65 [2024-11-06 22:54:55,234 INFO L226 Difference]: Without dead ends: 30 [2024-11-06 22:54:55,236 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 22:54:55,239 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:55,241 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:55,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-06 22:54:55,263 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-11-06 22:54:55,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-06 22:54:55,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2024-11-06 22:54:55,270 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2024-11-06 22:54:55,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:55,271 INFO L471 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2024-11-06 22:54:55,271 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-06 22:54:55,271 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2024-11-06 22:54:55,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-06 22:54:55,273 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:55,273 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:55,274 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-06 22:54:55,274 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:55,275 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:55,276 INFO L85 PathProgramCache]: Analyzing trace with hash -455220980, now seen corresponding path program 1 times [2024-11-06 22:54:55,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:55,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1142664180] [2024-11-06 22:54:55,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:55,276 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:55,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,425 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:55,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,440 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:55,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,448 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:55,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,458 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:55,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,466 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:55,466 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:55,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1142664180] [2024-11-06 22:54:55,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1142664180] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:55,467 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:55,467 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-06 22:54:55,467 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1570531352] [2024-11-06 22:54:55,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:55,468 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-06 22:54:55,468 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:55,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-06 22:54:55,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 22:54:55,469 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:55,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:55,498 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-06 22:54:55,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-06 22:54:55,499 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2024-11-06 22:54:55,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:55,500 INFO L225 Difference]: With dead ends: 40 [2024-11-06 22:54:55,500 INFO L226 Difference]: Without dead ends: 32 [2024-11-06 22:54:55,500 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 22:54:55,501 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 7 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:55,502 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:55,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2024-11-06 22:54:55,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2024-11-06 22:54:55,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-06 22:54:55,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2024-11-06 22:54:55,510 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2024-11-06 22:54:55,511 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:55,512 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2024-11-06 22:54:55,512 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:55,512 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2024-11-06 22:54:55,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-06 22:54:55,513 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:55,513 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:55,513 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-06 22:54:55,513 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:55,514 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:55,514 INFO L85 PathProgramCache]: Analyzing trace with hash -1233535180, now seen corresponding path program 1 times [2024-11-06 22:54:55,514 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:55,514 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1872452409] [2024-11-06 22:54:55,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:55,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:55,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:55,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,686 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:55,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:55,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,734 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:55,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,741 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-06 22:54:55,741 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:55,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1872452409] [2024-11-06 22:54:55,741 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1872452409] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:55,741 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1038488337] [2024-11-06 22:54:55,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:55,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:55,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:55,746 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:55,747 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-06 22:54:55,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:55,816 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:55,821 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:55,988 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:55,988 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:55,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1038488337] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:55,989 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:55,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-11-06 22:54:55,989 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1344274818] [2024-11-06 22:54:55,989 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:55,989 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:54:55,989 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:55,990 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:54:55,990 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2024-11-06 22:54:55,990 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-06 22:54:56,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:56,110 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2024-11-06 22:54:56,111 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:54:56,111 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-06 22:54:56,111 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:56,112 INFO L225 Difference]: With dead ends: 49 [2024-11-06 22:54:56,112 INFO L226 Difference]: Without dead ends: 47 [2024-11-06 22:54:56,112 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-06 22:54:56,113 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 9 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:56,113 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 146 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:56,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-06 22:54:56,125 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 45. [2024-11-06 22:54:56,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 28 states have internal predecessors, (34), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-06 22:54:56,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 63 transitions. [2024-11-06 22:54:56,128 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 63 transitions. Word has length 30 [2024-11-06 22:54:56,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:56,129 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 63 transitions. [2024-11-06 22:54:56,129 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-06 22:54:56,129 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 63 transitions. [2024-11-06 22:54:56,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-06 22:54:56,130 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:56,130 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:56,147 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-06 22:54:56,333 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:56,334 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:56,334 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:56,335 INFO L85 PathProgramCache]: Analyzing trace with hash -73118621, now seen corresponding path program 1 times [2024-11-06 22:54:56,335 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:56,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [84094270] [2024-11-06 22:54:56,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:56,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:56,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:56,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1825884229] [2024-11-06 22:54:56,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:56,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:56,385 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:56,387 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:56,389 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-06 22:54:56,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,448 INFO L255 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-06 22:54:56,449 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:56,506 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:56,507 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:56,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:56,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [84094270] [2024-11-06 22:54:56,508 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:56,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1825884229] [2024-11-06 22:54:56,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1825884229] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:56,508 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:56,508 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:56,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [993513232] [2024-11-06 22:54:56,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:56,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:56,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:56,509 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:56,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:56,509 INFO L87 Difference]: Start difference. First operand 45 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:56,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:56,563 INFO L93 Difference]: Finished difference Result 66 states and 95 transitions. [2024-11-06 22:54:56,563 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:56,563 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2024-11-06 22:54:56,563 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:56,565 INFO L225 Difference]: With dead ends: 66 [2024-11-06 22:54:56,565 INFO L226 Difference]: Without dead ends: 64 [2024-11-06 22:54:56,566 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:56,566 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:56,566 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 139 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:56,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-06 22:54:56,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2024-11-06 22:54:56,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 33 states have (on average 1.303030303030303) internal successors, (43), 37 states have internal predecessors, (43), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-06 22:54:56,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 76 transitions. [2024-11-06 22:54:56,586 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 76 transitions. Word has length 32 [2024-11-06 22:54:56,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:56,586 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 76 transitions. [2024-11-06 22:54:56,586 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:56,586 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2024-11-06 22:54:56,587 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-06 22:54:56,588 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:56,588 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:56,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-06 22:54:56,789 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:56,789 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:56,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:56,790 INFO L85 PathProgramCache]: Analyzing trace with hash -910809492, now seen corresponding path program 1 times [2024-11-06 22:54:56,790 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:56,790 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [663656120] [2024-11-06 22:54:56,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:56,790 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:56,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,875 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:56,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,878 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:56,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,901 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:56,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,907 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:56,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,911 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-06 22:54:56,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,913 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-06 22:54:56,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:56,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [663656120] [2024-11-06 22:54:56,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [663656120] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:56,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [333461309] [2024-11-06 22:54:56,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:56,914 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:56,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:56,916 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:56,918 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-06 22:54:56,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:56,970 INFO L255 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:56,972 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:57,075 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:57,076 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:57,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [333461309] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:57,076 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:57,076 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-06 22:54:57,076 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693610073] [2024-11-06 22:54:57,076 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:57,077 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:57,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:57,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:57,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-06 22:54:57,078 INFO L87 Difference]: Start difference. First operand 55 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-06 22:54:57,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:57,137 INFO L93 Difference]: Finished difference Result 63 states and 83 transitions. [2024-11-06 22:54:57,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:57,137 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 35 [2024-11-06 22:54:57,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:57,139 INFO L225 Difference]: With dead ends: 63 [2024-11-06 22:54:57,140 INFO L226 Difference]: Without dead ends: 59 [2024-11-06 22:54:57,140 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-06 22:54:57,141 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:57,142 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 142 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:57,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-11-06 22:54:57,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2024-11-06 22:54:57,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.25) internal successors, (45), 39 states have internal predecessors, (45), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-06 22:54:57,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 76 transitions. [2024-11-06 22:54:57,153 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 76 transitions. Word has length 35 [2024-11-06 22:54:57,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:57,153 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 76 transitions. [2024-11-06 22:54:57,154 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-06 22:54:57,154 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 76 transitions. [2024-11-06 22:54:57,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-06 22:54:57,154 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:57,155 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:57,170 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-06 22:54:57,355 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:57,355 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:57,356 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:57,356 INFO L85 PathProgramCache]: Analyzing trace with hash 96561445, now seen corresponding path program 1 times [2024-11-06 22:54:57,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:57,356 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1318262034] [2024-11-06 22:54:57,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:57,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:57,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,424 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:57,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,428 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:57,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:57,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,436 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:57,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,439 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 22:54:57,439 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:57,439 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1318262034] [2024-11-06 22:54:57,440 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1318262034] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:57,440 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:57,440 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:57,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2032216514] [2024-11-06 22:54:57,440 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:57,440 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:57,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:57,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:57,441 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:57,441 INFO L87 Difference]: Start difference. First operand 58 states and 76 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:57,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:57,465 INFO L93 Difference]: Finished difference Result 84 states and 111 transitions. [2024-11-06 22:54:57,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:57,466 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2024-11-06 22:54:57,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:57,467 INFO L225 Difference]: With dead ends: 84 [2024-11-06 22:54:57,467 INFO L226 Difference]: Without dead ends: 58 [2024-11-06 22:54:57,467 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:57,468 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 7 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:57,468 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 122 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:57,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-06 22:54:57,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2024-11-06 22:54:57,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.2222222222222223) internal successors, (44), 39 states have internal predecessors, (44), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-06 22:54:57,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 75 transitions. [2024-11-06 22:54:57,486 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 75 transitions. Word has length 35 [2024-11-06 22:54:57,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:57,487 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 75 transitions. [2024-11-06 22:54:57,487 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-06 22:54:57,488 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 75 transitions. [2024-11-06 22:54:57,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-06 22:54:57,490 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:57,490 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:57,490 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-06 22:54:57,490 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:57,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:57,491 INFO L85 PathProgramCache]: Analyzing trace with hash 2115683101, now seen corresponding path program 1 times [2024-11-06 22:54:57,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:57,491 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [905939203] [2024-11-06 22:54:57,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:57,491 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:57,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:57,518 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1576766263] [2024-11-06 22:54:57,518 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:57,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:57,518 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:57,520 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:57,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-06 22:54:57,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:57,583 INFO L255 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-06 22:54:57,586 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:57,784 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-06 22:54:57,784 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 22:54:57,784 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:57,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [905939203] [2024-11-06 22:54:57,785 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:57,785 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1576766263] [2024-11-06 22:54:57,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1576766263] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:54:57,785 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:54:57,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:54:57,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1957689667] [2024-11-06 22:54:57,785 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:57,786 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:57,786 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:57,786 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:57,786 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:54:57,787 INFO L87 Difference]: Start difference. First operand 58 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-06 22:54:57,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:57,867 INFO L93 Difference]: Finished difference Result 65 states and 81 transitions. [2024-11-06 22:54:57,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:57,871 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2024-11-06 22:54:57,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:57,872 INFO L225 Difference]: With dead ends: 65 [2024-11-06 22:54:57,872 INFO L226 Difference]: Without dead ends: 63 [2024-11-06 22:54:57,873 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:54:57,873 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:57,874 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 130 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:57,874 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-06 22:54:57,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2024-11-06 22:54:57,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-06 22:54:57,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 78 transitions. [2024-11-06 22:54:57,895 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 78 transitions. Word has length 47 [2024-11-06 22:54:57,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:57,895 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 78 transitions. [2024-11-06 22:54:57,895 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-06 22:54:57,895 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 78 transitions. [2024-11-06 22:54:57,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-11-06 22:54:57,898 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:57,898 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:54:57,916 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 22:54:58,099 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-11-06 22:54:58,100 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:58,100 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:58,100 INFO L85 PathProgramCache]: Analyzing trace with hash 559010241, now seen corresponding path program 1 times [2024-11-06 22:54:58,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:58,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2126225749] [2024-11-06 22:54:58,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:58,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:58,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:54:58,124 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1667796236] [2024-11-06 22:54:58,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:58,124 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:58,125 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:58,127 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:58,128 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-06 22:54:58,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,194 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-06 22:54:58,196 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:58,286 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:54:58,286 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:58,379 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-11-06 22:54:58,379 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:58,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2126225749] [2024-11-06 22:54:58,379 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:54:58,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1667796236] [2024-11-06 22:54:58,379 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1667796236] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:58,379 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:54:58,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-06 22:54:58,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [646505279] [2024-11-06 22:54:58,380 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:54:58,380 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:54:58,380 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:58,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:54:58,380 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-06 22:54:58,381 INFO L87 Difference]: Start difference. First operand 62 states and 78 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-06 22:54:58,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:58,437 INFO L93 Difference]: Finished difference Result 68 states and 83 transitions. [2024-11-06 22:54:58,438 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:54:58,438 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 55 [2024-11-06 22:54:58,438 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:58,439 INFO L225 Difference]: With dead ends: 68 [2024-11-06 22:54:58,441 INFO L226 Difference]: Without dead ends: 66 [2024-11-06 22:54:58,441 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:54:58,442 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:58,442 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 124 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:54:58,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2024-11-06 22:54:58,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 58. [2024-11-06 22:54:58,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-06 22:54:58,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2024-11-06 22:54:58,454 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 55 [2024-11-06 22:54:58,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:58,454 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2024-11-06 22:54:58,454 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-06 22:54:58,454 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2024-11-06 22:54:58,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-06 22:54:58,455 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:58,455 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 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 22:54:58,472 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-06 22:54:58,659 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:58,660 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:58,660 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:58,660 INFO L85 PathProgramCache]: Analyzing trace with hash -879665460, now seen corresponding path program 1 times [2024-11-06 22:54:58,660 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:58,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2100903744] [2024-11-06 22:54:58,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:58,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:58,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,774 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:58,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,779 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:58,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,784 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:58,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,790 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:58,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,795 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-06 22:54:58,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,800 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:54:58,802 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,805 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-06 22:54:58,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,812 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:54:58,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,816 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:54:58,816 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:58,816 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2100903744] [2024-11-06 22:54:58,816 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2100903744] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:58,817 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [418943626] [2024-11-06 22:54:58,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:58,817 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:58,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:58,819 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:58,821 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-06 22:54:58,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:58,877 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-06 22:54:58,879 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:58,962 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:54:58,963 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:59,057 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:54:59,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [418943626] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:59,058 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:54:59,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-06 22:54:59,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1490184395] [2024-11-06 22:54:59,058 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:59,058 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-06 22:54:59,058 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:59,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-06 22:54:59,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-06 22:54:59,059 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-06 22:54:59,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:54:59,246 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2024-11-06 22:54:59,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-06 22:54:59,247 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 56 [2024-11-06 22:54:59,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:54:59,249 INFO L225 Difference]: With dead ends: 211 [2024-11-06 22:54:59,250 INFO L226 Difference]: Without dead ends: 203 [2024-11-06 22:54:59,251 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:54:59,252 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 65 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:54:59,252 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 186 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:54:59,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2024-11-06 22:54:59,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2024-11-06 22:54:59,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-06 22:54:59,299 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2024-11-06 22:54:59,301 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2024-11-06 22:54:59,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:54:59,301 INFO L471 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2024-11-06 22:54:59,301 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-06 22:54:59,301 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2024-11-06 22:54:59,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-06 22:54:59,302 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:54:59,304 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 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 22:54:59,321 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-06 22:54:59,505 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-06 22:54:59,505 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:54:59,505 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:54:59,506 INFO L85 PathProgramCache]: Analyzing trace with hash -1506412172, now seen corresponding path program 1 times [2024-11-06 22:54:59,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:54:59,506 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [844064549] [2024-11-06 22:54:59,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:59,506 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:54:59,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,654 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:54:59,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,677 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:54:59,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:54:59,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,684 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:54:59,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-06 22:54:59,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,691 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:54:59,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,694 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-06 22:54:59,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,700 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:54:59,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,708 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:59,711 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:54:59,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [844064549] [2024-11-06 22:54:59,711 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [844064549] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:54:59,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [202375531] [2024-11-06 22:54:59,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:54:59,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:54:59,712 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:54:59,714 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:54:59,716 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-06 22:54:59,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:54:59,779 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 22:54:59,780 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:54:59,825 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:59,825 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:54:59,925 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-06 22:54:59,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [202375531] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:54:59,925 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:54:59,925 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-06 22:54:59,925 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1154500746] [2024-11-06 22:54:59,925 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:54:59,926 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-06 22:54:59,926 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:54:59,926 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-06 22:54:59,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-06 22:54:59,927 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-06 22:55:00,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:00,129 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2024-11-06 22:55:00,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-06 22:55:00,130 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2024-11-06 22:55:00,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:00,132 INFO L225 Difference]: With dead ends: 279 [2024-11-06 22:55:00,132 INFO L226 Difference]: Without dead ends: 259 [2024-11-06 22:55:00,132 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 124 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:55:00,133 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 60 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:00,133 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 249 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:55:00,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2024-11-06 22:55:00,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2024-11-06 22:55:00,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-06 22:55:00,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2024-11-06 22:55:00,178 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2024-11-06 22:55:00,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:00,179 INFO L471 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2024-11-06 22:55:00,179 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-06 22:55:00,179 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2024-11-06 22:55:00,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-06 22:55:00,180 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:00,180 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 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 22:55:00,196 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-06 22:55:00,380 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:00,381 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:00,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:00,381 INFO L85 PathProgramCache]: Analyzing trace with hash -1869160295, now seen corresponding path program 1 times [2024-11-06 22:55:00,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:00,381 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294423922] [2024-11-06 22:55:00,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:00,381 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:00,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,465 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:55:00,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,468 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:55:00,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,470 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:55:00,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,473 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:55:00,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,476 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-06 22:55:00,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,478 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:55:00,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-06 22:55:00,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,484 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:55:00,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,487 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:55:00,488 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:00,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294423922] [2024-11-06 22:55:00,488 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [294423922] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:00,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1541434676] [2024-11-06 22:55:00,488 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:00,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:00,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:00,490 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:00,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-06 22:55:00,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:00,550 INFO L255 TraceCheckSpWp]: Trace formula consists of 172 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-06 22:55:00,553 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:00,629 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:55:00,629 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:00,718 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 22:55:00,719 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1541434676] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:55:00,719 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:55:00,719 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 6] total 10 [2024-11-06 22:55:00,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [81920880] [2024-11-06 22:55:00,719 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:00,720 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-06 22:55:00,720 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:00,721 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-06 22:55:00,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-11-06 22:55:00,721 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-06 22:55:00,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:00,892 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2024-11-06 22:55:00,893 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-06 22:55:00,893 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) Word has length 59 [2024-11-06 22:55:00,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:00,895 INFO L225 Difference]: With dead ends: 344 [2024-11-06 22:55:00,895 INFO L226 Difference]: Without dead ends: 248 [2024-11-06 22:55:00,895 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:55:00,896 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 70 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 94 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:00,896 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 183 Invalid, 94 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:55:00,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2024-11-06 22:55:00,925 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2024-11-06 22:55:00,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2024-11-06 22:55:00,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2024-11-06 22:55:00,928 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2024-11-06 22:55:00,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:00,928 INFO L471 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2024-11-06 22:55:00,929 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (24), 4 states have call predecessors, (24), 4 states have call successors, (24) [2024-11-06 22:55:00,929 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2024-11-06 22:55:00,929 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-11-06 22:55:00,929 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:00,930 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:00,947 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 22:55:01,133 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,9 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:01,134 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:01,134 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:01,134 INFO L85 PathProgramCache]: Analyzing trace with hash 991223133, now seen corresponding path program 1 times [2024-11-06 22:55:01,135 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:01,135 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1694478364] [2024-11-06 22:55:01,135 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:01,135 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:01,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:01,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [486059014] [2024-11-06 22:55:01,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:01,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:01,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:01,157 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 22:55:01,158 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 22:55:01,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:01,225 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-06 22:55:01,227 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:01,395 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-06 22:55:01,395 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:01,444 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:01,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1694478364] [2024-11-06 22:55:01,444 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:01,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [486059014] [2024-11-06 22:55:01,444 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [486059014] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:01,445 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:55:01,445 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2024-11-06 22:55:01,445 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2044432394] [2024-11-06 22:55:01,445 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:01,445 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:55:01,445 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:01,446 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:55:01,446 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-11-06 22:55:01,446 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-06 22:55:01,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:01,577 INFO L93 Difference]: Finished difference Result 283 states and 355 transitions. [2024-11-06 22:55:01,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:55:01,578 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 64 [2024-11-06 22:55:01,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:01,580 INFO L225 Difference]: With dead ends: 283 [2024-11-06 22:55:01,581 INFO L226 Difference]: Without dead ends: 278 [2024-11-06 22:55:01,581 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:55:01,583 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 10 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:01,584 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 213 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:55:01,584 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 278 states. [2024-11-06 22:55:01,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 278 to 276. [2024-11-06 22:55:01,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 276 states, 183 states have (on average 1.185792349726776) internal successors, (217), 187 states have internal predecessors, (217), 65 states have call successors, (65), 27 states have call predecessors, (65), 27 states have return successors, (61), 61 states have call predecessors, (61), 61 states have call successors, (61) [2024-11-06 22:55:01,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 276 states to 276 states and 343 transitions. [2024-11-06 22:55:01,625 INFO L78 Accepts]: Start accepts. Automaton has 276 states and 343 transitions. Word has length 64 [2024-11-06 22:55:01,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:01,625 INFO L471 AbstractCegarLoop]: Abstraction has 276 states and 343 transitions. [2024-11-06 22:55:01,626 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-06 22:55:01,626 INFO L276 IsEmpty]: Start isEmpty. Operand 276 states and 343 transitions. [2024-11-06 22:55:01,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2024-11-06 22:55:01,627 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:01,627 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:01,644 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 22:55:01,830 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:01,831 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:01,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:01,832 INFO L85 PathProgramCache]: Analyzing trace with hash 1694315171, now seen corresponding path program 2 times [2024-11-06 22:55:01,832 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:01,832 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [586687396] [2024-11-06 22:55:01,832 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:01,832 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:01,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:01,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1652006961] [2024-11-06 22:55:01,856 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-06 22:55:01,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:01,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:01,858 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 22:55:01,860 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 22:55:01,928 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-06 22:55:01,929 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:55:01,930 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-06 22:55:01,932 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:02,386 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 20 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-06 22:55:02,386 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:02,557 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-06 22:55:02,557 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:02,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [586687396] [2024-11-06 22:55:02,557 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:02,557 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1652006961] [2024-11-06 22:55:02,557 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1652006961] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:55:02,557 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 22:55:02,557 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 14 [2024-11-06 22:55:02,558 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [162969028] [2024-11-06 22:55:02,558 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:02,558 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-06 22:55:02,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:02,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-06 22:55:02,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:55:02,559 INFO L87 Difference]: Start difference. First operand 276 states and 343 transitions. Second operand has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 11 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-06 22:55:03,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:03,106 INFO L93 Difference]: Finished difference Result 294 states and 361 transitions. [2024-11-06 22:55:03,107 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-06 22:55:03,108 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 11 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) Word has length 69 [2024-11-06 22:55:03,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:03,110 INFO L225 Difference]: With dead ends: 294 [2024-11-06 22:55:03,110 INFO L226 Difference]: Without dead ends: 290 [2024-11-06 22:55:03,111 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 122 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=117, Invalid=389, Unknown=0, NotChecked=0, Total=506 [2024-11-06 22:55:03,112 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 60 mSDsluCounter, 291 mSDsCounter, 0 mSdLazyCounter, 210 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 330 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 210 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:03,112 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 330 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 210 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 22:55:03,113 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 290 states. [2024-11-06 22:55:03,162 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 290 to 286. [2024-11-06 22:55:03,163 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 286 states, 192 states have (on average 1.1770833333333333) internal successors, (226), 195 states have internal predecessors, (226), 63 states have call successors, (63), 30 states have call predecessors, (63), 30 states have return successors, (60), 60 states have call predecessors, (60), 60 states have call successors, (60) [2024-11-06 22:55:03,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 286 states to 286 states and 349 transitions. [2024-11-06 22:55:03,167 INFO L78 Accepts]: Start accepts. Automaton has 286 states and 349 transitions. Word has length 69 [2024-11-06 22:55:03,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:03,167 INFO L471 AbstractCegarLoop]: Abstraction has 286 states and 349 transitions. [2024-11-06 22:55:03,167 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.076923076923077) internal successors, (40), 11 states have internal predecessors, (40), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-06 22:55:03,167 INFO L276 IsEmpty]: Start isEmpty. Operand 286 states and 349 transitions. [2024-11-06 22:55:03,168 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-06 22:55:03,168 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:03,168 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:03,185 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 22:55:03,368 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,SelfDestructingSolverStorable12 [2024-11-06 22:55:03,369 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:03,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:03,369 INFO L85 PathProgramCache]: Analyzing trace with hash -1349365539, now seen corresponding path program 3 times [2024-11-06 22:55:03,369 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:03,369 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657823520] [2024-11-06 22:55:03,369 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:03,369 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:03,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:03,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [67932128] [2024-11-06 22:55:03,403 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-06 22:55:03,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:03,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:03,406 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 22:55:03,408 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 22:55:03,472 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-06 22:55:03,473 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:55:03,475 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-11-06 22:55:03,477 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:04,632 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 42 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-06 22:55:04,633 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:34,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:34,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [657823520] [2024-11-06 22:55:34,715 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:34,715 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [67932128] [2024-11-06 22:55:34,715 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [67932128] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:34,715 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:55:34,715 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-06 22:55:34,715 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1092689600] [2024-11-06 22:55:34,715 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:34,715 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-06 22:55:34,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:34,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-06 22:55:34,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=535, Unknown=1, NotChecked=0, Total=650 [2024-11-06 22:55:34,716 INFO L87 Difference]: Start difference. First operand 286 states and 349 transitions. Second operand has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-06 22:55:35,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:35,362 INFO L93 Difference]: Finished difference Result 309 states and 369 transitions. [2024-11-06 22:55:35,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-06 22:55:35,363 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 74 [2024-11-06 22:55:35,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:35,365 INFO L225 Difference]: With dead ends: 309 [2024-11-06 22:55:35,365 INFO L226 Difference]: Without dead ends: 305 [2024-11-06 22:55:35,365 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 24.9s TimeCoverageRelationStatistics Valid=167, Invalid=702, Unknown=1, NotChecked=0, Total=870 [2024-11-06 22:55:35,366 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 37 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 293 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 294 SdHoareTripleChecker+Invalid, 305 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 293 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:35,366 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 294 Invalid, 305 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 293 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 22:55:35,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 305 states. [2024-11-06 22:55:35,407 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 305 to 304. [2024-11-06 22:55:35,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 304 states, 206 states have (on average 1.1601941747572815) internal successors, (239), 208 states have internal predecessors, (239), 63 states have call successors, (63), 35 states have call predecessors, (63), 34 states have return successors, (60), 60 states have call predecessors, (60), 60 states have call successors, (60) [2024-11-06 22:55:35,411 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 304 states to 304 states and 362 transitions. [2024-11-06 22:55:35,412 INFO L78 Accepts]: Start accepts. Automaton has 304 states and 362 transitions. Word has length 74 [2024-11-06 22:55:35,412 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:35,412 INFO L471 AbstractCegarLoop]: Abstraction has 304 states and 362 transitions. [2024-11-06 22:55:35,413 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-06 22:55:35,413 INFO L276 IsEmpty]: Start isEmpty. Operand 304 states and 362 transitions. [2024-11-06 22:55:35,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-06 22:55:35,413 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:35,414 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:35,427 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-06 22:55:35,614 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-06 22:55:35,614 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:35,614 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:35,614 INFO L85 PathProgramCache]: Analyzing trace with hash -484140586, now seen corresponding path program 1 times [2024-11-06 22:55:35,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:35,615 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143053362] [2024-11-06 22:55:35,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:35,615 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:35,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:35,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1753233943] [2024-11-06 22:55:35,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:35,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:35,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:35,638 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:35,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-06 22:55:35,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:35,710 INFO L255 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-06 22:55:35,712 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:36,178 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-06 22:55:36,178 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:37,187 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-06 22:55:37,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:37,187 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143053362] [2024-11-06 22:55:37,188 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:37,188 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1753233943] [2024-11-06 22:55:37,188 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1753233943] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:55:37,188 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 22:55:37,188 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-06 22:55:37,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2136068081] [2024-11-06 22:55:37,188 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:37,188 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-06 22:55:37,188 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:37,189 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-06 22:55:37,189 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-06 22:55:37,189 INFO L87 Difference]: Start difference. First operand 304 states and 362 transitions. Second operand has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-06 22:55:39,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:39,614 INFO L93 Difference]: Finished difference Result 440 states and 579 transitions. [2024-11-06 22:55:39,615 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-06 22:55:39,615 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 80 [2024-11-06 22:55:39,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:39,617 INFO L225 Difference]: With dead ends: 440 [2024-11-06 22:55:39,617 INFO L226 Difference]: Without dead ends: 425 [2024-11-06 22:55:39,618 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 139 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=296, Invalid=1264, Unknown=0, NotChecked=0, Total=1560 [2024-11-06 22:55:39,618 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 136 mSDsluCounter, 578 mSDsCounter, 0 mSdLazyCounter, 533 mSolverCounterSat, 126 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 140 SdHoareTripleChecker+Valid, 634 SdHoareTripleChecker+Invalid, 659 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 126 IncrementalHoareTripleChecker+Valid, 533 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:39,618 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [140 Valid, 634 Invalid, 659 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [126 Valid, 533 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-06 22:55:39,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 425 states. [2024-11-06 22:55:39,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 425 to 392. [2024-11-06 22:55:39,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 392 states, 259 states have (on average 1.22007722007722) internal successors, (316), 260 states have internal predecessors, (316), 97 states have call successors, (97), 35 states have call predecessors, (97), 35 states have return successors, (96), 96 states have call predecessors, (96), 96 states have call successors, (96) [2024-11-06 22:55:39,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 392 states to 392 states and 509 transitions. [2024-11-06 22:55:39,703 INFO L78 Accepts]: Start accepts. Automaton has 392 states and 509 transitions. Word has length 80 [2024-11-06 22:55:39,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:39,704 INFO L471 AbstractCegarLoop]: Abstraction has 392 states and 509 transitions. [2024-11-06 22:55:39,704 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3157894736842106) internal successors, (44), 18 states have internal predecessors, (44), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-06 22:55:39,704 INFO L276 IsEmpty]: Start isEmpty. Operand 392 states and 509 transitions. [2024-11-06 22:55:39,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-06 22:55:39,705 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:39,705 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:39,722 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-06 22:55:39,905 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,13 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:39,905 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:39,905 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:39,906 INFO L85 PathProgramCache]: Analyzing trace with hash -1718599493, now seen corresponding path program 1 times [2024-11-06 22:55:39,906 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:39,906 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [839131869] [2024-11-06 22:55:39,906 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:39,906 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:39,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:39,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1023172213] [2024-11-06 22:55:39,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:39,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:39,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:39,927 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:39,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-06 22:55:40,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:40,002 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-11-06 22:55:40,004 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:41,033 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 51 proven. 32 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2024-11-06 22:55:41,033 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:41,144 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:41,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [839131869] [2024-11-06 22:55:41,144 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:41,144 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1023172213] [2024-11-06 22:55:41,144 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1023172213] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:41,144 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:55:41,144 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-11-06 22:55:41,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1059469684] [2024-11-06 22:55:41,145 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:41,145 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-06 22:55:41,145 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:41,145 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-06 22:55:41,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2024-11-06 22:55:41,146 INFO L87 Difference]: Start difference. First operand 392 states and 509 transitions. Second operand has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-06 22:55:42,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:42,108 INFO L93 Difference]: Finished difference Result 401 states and 517 transitions. [2024-11-06 22:55:42,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-06 22:55:42,109 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 97 [2024-11-06 22:55:42,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:42,113 INFO L225 Difference]: With dead ends: 401 [2024-11-06 22:55:42,114 INFO L226 Difference]: Without dead ends: 399 [2024-11-06 22:55:42,115 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=84, Invalid=422, Unknown=0, NotChecked=0, Total=506 [2024-11-06 22:55:42,115 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 42 mSDsluCounter, 278 mSDsCounter, 0 mSdLazyCounter, 391 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 323 SdHoareTripleChecker+Invalid, 403 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 391 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:42,116 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 323 Invalid, 403 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 391 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-06 22:55:42,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 399 states. [2024-11-06 22:55:42,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 399 to 396. [2024-11-06 22:55:42,210 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 396 states, 262 states have (on average 1.213740458015267) internal successors, (318), 263 states have internal predecessors, (318), 97 states have call successors, (97), 36 states have call predecessors, (97), 36 states have return successors, (96), 96 states have call predecessors, (96), 96 states have call successors, (96) [2024-11-06 22:55:42,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 396 states to 396 states and 511 transitions. [2024-11-06 22:55:42,213 INFO L78 Accepts]: Start accepts. Automaton has 396 states and 511 transitions. Word has length 97 [2024-11-06 22:55:42,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:42,213 INFO L471 AbstractCegarLoop]: Abstraction has 396 states and 511 transitions. [2024-11-06 22:55:42,213 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.2) internal successors, (33), 13 states have internal predecessors, (33), 7 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2024-11-06 22:55:42,213 INFO L276 IsEmpty]: Start isEmpty. Operand 396 states and 511 transitions. [2024-11-06 22:55:42,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-06 22:55:42,214 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:42,214 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:42,233 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-06 22:55:42,416 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,14 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:42,416 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:42,416 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:42,417 INFO L85 PathProgramCache]: Analyzing trace with hash 160443165, now seen corresponding path program 4 times [2024-11-06 22:55:42,417 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:42,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1235772953] [2024-11-06 22:55:42,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:42,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:42,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,486 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:55:42,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,488 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:55:42,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,490 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:55:42,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,491 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:55:42,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,492 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-06 22:55:42,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,493 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:55:42,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,495 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-06 22:55:42,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,496 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:55:42,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,498 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2024-11-06 22:55:42,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,500 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-06 22:55:42,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,504 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-06 22:55:42,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,507 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-06 22:55:42,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,510 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 82 [2024-11-06 22:55:42,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,515 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 87 [2024-11-06 22:55:42,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,517 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-06 22:55:42,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,519 INFO L134 CoverageAnalysis]: Checked inductivity of 295 backedges. 51 proven. 0 refuted. 0 times theorem prover too weak. 244 trivial. 0 not checked. [2024-11-06 22:55:42,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:42,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1235772953] [2024-11-06 22:55:42,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1235772953] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:55:42,519 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:55:42,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:55:42,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1399170253] [2024-11-06 22:55:42,519 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:55:42,520 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:55:42,520 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:42,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:55:42,520 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:55:42,520 INFO L87 Difference]: Start difference. First operand 396 states and 511 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-06 22:55:42,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:42,645 INFO L93 Difference]: Finished difference Result 588 states and 820 transitions. [2024-11-06 22:55:42,646 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:55:42,646 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 101 [2024-11-06 22:55:42,646 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:42,649 INFO L225 Difference]: With dead ends: 588 [2024-11-06 22:55:42,649 INFO L226 Difference]: Without dead ends: 465 [2024-11-06 22:55:42,650 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-11-06 22:55:42,651 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 12 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:42,651 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 174 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:55:42,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 465 states. [2024-11-06 22:55:42,737 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 465 to 415. [2024-11-06 22:55:42,738 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 415 states, 273 states have (on average 1.2234432234432235) internal successors, (334), 274 states have internal predecessors, (334), 105 states have call successors, (105), 36 states have call predecessors, (105), 36 states have return successors, (104), 104 states have call predecessors, (104), 104 states have call successors, (104) [2024-11-06 22:55:42,740 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 415 states to 415 states and 543 transitions. [2024-11-06 22:55:42,741 INFO L78 Accepts]: Start accepts. Automaton has 415 states and 543 transitions. Word has length 101 [2024-11-06 22:55:42,741 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:42,741 INFO L471 AbstractCegarLoop]: Abstraction has 415 states and 543 transitions. [2024-11-06 22:55:42,741 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 5 states have internal predecessors, (31), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-06 22:55:42,741 INFO L276 IsEmpty]: Start isEmpty. Operand 415 states and 543 transitions. [2024-11-06 22:55:42,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2024-11-06 22:55:42,743 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:42,743 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:42,743 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable16 [2024-11-06 22:55:42,743 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:42,743 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:42,743 INFO L85 PathProgramCache]: Analyzing trace with hash -245423741, now seen corresponding path program 1 times [2024-11-06 22:55:42,744 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:42,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [210789339] [2024-11-06 22:55:42,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:42,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:42,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,944 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-06 22:55:42,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,947 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-06 22:55:42,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-06 22:55:42,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,951 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-06 22:55:42,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,954 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-06 22:55:42,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,958 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-06 22:55:42,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-06 22:55:42,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,963 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-06 22:55:42,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 55 [2024-11-06 22:55:42,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-06 22:55:42,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,970 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-06 22:55:42,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,974 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-06 22:55:42,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,976 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-06 22:55:42,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,983 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-06 22:55:42,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,990 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-06 22:55:42,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,993 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-06 22:55:42,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:42,998 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-06 22:55:43,000 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:43,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [210789339] [2024-11-06 22:55:43,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [210789339] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:43,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1625789272] [2024-11-06 22:55:43,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:43,000 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:43,000 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:43,002 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:43,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-06 22:55:43,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:55:43,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 298 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-06 22:55:43,084 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:43,173 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 229 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2024-11-06 22:55:43,173 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:43,287 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2024-11-06 22:55:43,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1625789272] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:55:43,288 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:55:43,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 10] total 14 [2024-11-06 22:55:43,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [152146884] [2024-11-06 22:55:43,288 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:43,288 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-06 22:55:43,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:43,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-06 22:55:43,289 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2024-11-06 22:55:43,289 INFO L87 Difference]: Start difference. First operand 415 states and 543 transitions. Second operand has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (45), 6 states have call predecessors, (45), 5 states have return successors, (44), 7 states have call predecessors, (44), 7 states have call successors, (44) [2024-11-06 22:55:43,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:43,715 INFO L93 Difference]: Finished difference Result 1012 states and 1360 transitions. [2024-11-06 22:55:43,715 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-06 22:55:43,715 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (45), 6 states have call predecessors, (45), 5 states have return successors, (44), 7 states have call predecessors, (44), 7 states have call successors, (44) Word has length 112 [2024-11-06 22:55:43,716 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:43,721 INFO L225 Difference]: With dead ends: 1012 [2024-11-06 22:55:43,721 INFO L226 Difference]: Without dead ends: 855 [2024-11-06 22:55:43,722 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 271 GetRequests, 247 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=165, Invalid=297, Unknown=0, NotChecked=0, Total=462 [2024-11-06 22:55:43,722 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 92 mSDsluCounter, 191 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:43,723 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 229 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-06 22:55:43,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 855 states. [2024-11-06 22:55:43,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 855 to 825. [2024-11-06 22:55:43,881 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 825 states, 532 states have (on average 1.1860902255639099) internal successors, (631), 536 states have internal predecessors, (631), 212 states have call successors, (212), 80 states have call predecessors, (212), 80 states have return successors, (208), 208 states have call predecessors, (208), 208 states have call successors, (208) [2024-11-06 22:55:43,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 825 states to 825 states and 1051 transitions. [2024-11-06 22:55:43,885 INFO L78 Accepts]: Start accepts. Automaton has 825 states and 1051 transitions. Word has length 112 [2024-11-06 22:55:43,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:43,886 INFO L471 AbstractCegarLoop]: Abstraction has 825 states and 1051 transitions. [2024-11-06 22:55:43,886 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (45), 6 states have call predecessors, (45), 5 states have return successors, (44), 7 states have call predecessors, (44), 7 states have call successors, (44) [2024-11-06 22:55:43,886 INFO L276 IsEmpty]: Start isEmpty. Operand 825 states and 1051 transitions. [2024-11-06 22:55:43,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2024-11-06 22:55:43,887 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:43,887 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:43,904 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-06 22:55:44,088 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-06 22:55:44,088 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:44,088 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:44,088 INFO L85 PathProgramCache]: Analyzing trace with hash -1062250723, now seen corresponding path program 2 times [2024-11-06 22:55:44,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:44,088 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493192699] [2024-11-06 22:55:44,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:44,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:44,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:44,119 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [365083949] [2024-11-06 22:55:44,120 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-06 22:55:44,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:44,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:44,122 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:44,123 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-06 22:55:44,200 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-06 22:55:44,200 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:55:44,204 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 56 conjuncts are in the unsatisfiable core [2024-11-06 22:55:44,206 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:45,092 INFO L134 CoverageAnalysis]: Checked inductivity of 516 backedges. 103 proven. 56 refuted. 0 times theorem prover too weak. 357 trivial. 0 not checked. [2024-11-06 22:55:45,092 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:55:55,596 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse0 (+ (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|))) (.cse1 (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|)) (.cse2 (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|))) (or (= .cse0 (+ .cse1 .cse2)) (not (= .cse0 (+ |c_ULTIMATE.start_main_~c~0#1| .cse1 .cse2))) (< |c_ULTIMATE.start_main_~b~0#1| (+ |c_ULTIMATE.start_main_~c~0#1| 1)) (forall ((|ULTIMATE.start_main_~yy~0#1| Int)) (or (= (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~p~0#1|)) (+ (* |ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~r~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~p~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|))) (not (= (+ (* |ULTIMATE.start_main_~yy~0#1| |c_ULTIMATE.start_main_~s~0#1|) (* |c_ULTIMATE.start_main_~xy~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~b~0#1|) (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|) (* |c_ULTIMATE.start_main_~x~0#1| |c_ULTIMATE.start_main_~q~0#1|) (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~b~0#1|)))))))) is different from true [2024-11-06 22:55:55,597 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:55:55,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493192699] [2024-11-06 22:55:55,597 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-06 22:55:55,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [365083949] [2024-11-06 22:55:55,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [365083949] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:55:55,597 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-06 22:55:55,597 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-11-06 22:55:55,597 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866183050] [2024-11-06 22:55:55,597 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-06 22:55:55,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-06 22:55:55,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:55:55,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-06 22:55:55,598 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=468, Unknown=1, NotChecked=44, Total=600 [2024-11-06 22:55:55,598 INFO L87 Difference]: Start difference. First operand 825 states and 1051 transitions. Second operand has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 6 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-06 22:55:56,221 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:55:56,221 INFO L93 Difference]: Finished difference Result 882 states and 1113 transitions. [2024-11-06 22:55:56,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-06 22:55:56,221 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 6 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) Word has length 120 [2024-11-06 22:55:56,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:55:56,226 INFO L225 Difference]: With dead ends: 882 [2024-11-06 22:55:56,226 INFO L226 Difference]: Without dead ends: 880 [2024-11-06 22:55:56,227 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 123 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=138, Invalid=735, Unknown=1, NotChecked=56, Total=930 [2024-11-06 22:55:56,227 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 41 mSDsluCounter, 389 mSDsCounter, 0 mSdLazyCounter, 521 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 433 SdHoareTripleChecker+Invalid, 557 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 521 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:55:56,227 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 433 Invalid, 557 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 521 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 22:55:56,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 880 states. [2024-11-06 22:55:56,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 880 to 830. [2024-11-06 22:55:56,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 830 states, 538 states have (on average 1.1802973977695168) internal successors, (635), 542 states have internal predecessors, (635), 208 states have call successors, (208), 83 states have call predecessors, (208), 83 states have return successors, (204), 204 states have call predecessors, (204), 204 states have call successors, (204) [2024-11-06 22:55:56,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 830 states to 830 states and 1047 transitions. [2024-11-06 22:55:56,383 INFO L78 Accepts]: Start accepts. Automaton has 830 states and 1047 transitions. Word has length 120 [2024-11-06 22:55:56,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:55:56,384 INFO L471 AbstractCegarLoop]: Abstraction has 830 states and 1047 transitions. [2024-11-06 22:55:56,384 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.1176470588235294) internal successors, (36), 14 states have internal predecessors, (36), 6 states have call successors, (20), 2 states have call predecessors, (20), 3 states have return successors, (19), 8 states have call predecessors, (19), 6 states have call successors, (19) [2024-11-06 22:55:56,384 INFO L276 IsEmpty]: Start isEmpty. Operand 830 states and 1047 transitions. [2024-11-06 22:55:56,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-06 22:55:56,387 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:55:56,387 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:55:56,404 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-06 22:55:56,591 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,16 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:56,592 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:55:56,592 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:55:56,592 INFO L85 PathProgramCache]: Analyzing trace with hash -1493115269, now seen corresponding path program 3 times [2024-11-06 22:55:56,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:55:56,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [398165220] [2024-11-06 22:55:56,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:55:56,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:55:56,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-06 22:55:56,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1602076856] [2024-11-06 22:55:56,621 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-06 22:55:56,622 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:55:56,622 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:55:56,624 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 22:55:56,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-06 22:55:56,751 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-06 22:55:56,752 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-06 22:55:56,753 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 62 conjuncts are in the unsatisfiable core [2024-11-06 22:55:56,756 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:55:57,975 INFO L134 CoverageAnalysis]: Checked inductivity of 523 backedges. 100 proven. 57 refuted. 0 times theorem prover too weak. 366 trivial. 0 not checked. [2024-11-06 22:55:57,975 INFO L311 TraceCheckSpWp]: Computing backward predicates...