./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/heap-manipulation/dancing.i --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/heap-manipulation/dancing.i', '-s', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf', '--cacsl2boogietranslator.entry.function', 'main', '--witnessprinter.witness.directory', '/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux', '--witnessprinter.witness.filename', 'witness', '--witnessprinter.write.witness.besides.input.file', 'false', '--witnessprinter.graph.data.specification', 'CHECK( init(main()), LTL(G ! call(reach_error())) )\n\n', '--witnessprinter.graph.data.producer', 'Automizer', '--witnessprinter.graph.data.architecture', '32bit', '--witnessprinter.graph.data.programhash', 'c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a'] 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/heap-manipulation/dancing.i -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a --- Real Ultimate output --- This is Ultimate 0.3.0-?-4f9af40 [2024-11-06 22:21:15,692 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 22:21:15,787 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:21:15,792 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 22:21:15,792 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 22:21:15,823 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 22:21:15,823 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 22:21:15,824 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 22:21:15,824 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 22:21:15,824 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 22:21:15,824 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 22:21:15,824 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 22:21:15,825 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 22:21:15,825 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 22:21:15,825 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 22:21:15,826 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 22:21:15,826 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 22:21:15,828 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 22:21:15,828 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:21:15,829 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-06 22:21:15,829 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-06 22:21:15,830 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 22:21:15,830 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 22:21:15,830 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 22:21:15,830 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 22:21:15,831 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 -> c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a [2024-11-06 22:21:16,136 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 22:21:16,144 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 22:21:16,147 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 22:21:16,148 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 22:21:16,149 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 22:21:16,150 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/dancing.i [2024-11-06 22:21:17,436 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 22:21:17,679 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 22:21:17,680 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i [2024-11-06 22:21:17,690 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/f869b584a/869930a19d6d4f6883c3fd3c77f2b408/FLAG6a35ec2e0 [2024-11-06 22:21:17,709 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/f869b584a/869930a19d6d4f6883c3fd3c77f2b408 [2024-11-06 22:21:17,712 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 22:21:17,713 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-06 22:21:17,714 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 22:21:17,714 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 22:21:17,718 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 22:21:17,719 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:21:17" (1/1) ... [2024-11-06 22:21:17,720 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@64e9bf70 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:17, skipping insertion in model container [2024-11-06 22:21:17,720 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 10:21:17" (1/1) ... [2024-11-06 22:21:17,742 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 22:21:17,879 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/heap-manipulation/dancing.i[938,951] [2024-11-06 22:21:17,982 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:21:17,996 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 22:21:18,006 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/heap-manipulation/dancing.i[938,951] [2024-11-06 22:21:18,033 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 22:21:18,057 INFO L204 MainTranslator]: Completed translation [2024-11-06 22:21:18,058 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18 WrapperNode [2024-11-06 22:21:18,058 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 22:21:18,059 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 22:21:18,059 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 22:21:18,059 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 22:21:18,064 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:21:18" (1/1) ... [2024-11-06 22:21:18,083 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:21:18" (1/1) ... [2024-11-06 22:21:18,107 INFO L138 Inliner]: procedures = 124, calls = 40, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 88 [2024-11-06 22:21:18,108 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 22:21:18,109 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 22:21:18,109 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 22:21:18,110 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 22:21:18,117 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,118 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,122 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,143 INFO L175 MemorySlicer]: Split 23 memory accesses to 2 slices as follows [2, 21]. 91 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 9 writes are split as follows [0, 9]. [2024-11-06 22:21:18,143 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,143 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,151 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,154 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,157 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,158 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,160 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 22:21:18,165 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 22:21:18,166 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 22:21:18,166 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 22:21:18,167 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (1/1) ... [2024-11-06 22:21:18,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 22:21:18,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:21:18,198 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:21:18,200 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:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure is_list_containing_x [2024-11-06 22:21:18,222 INFO L138 BoogieDeclarations]: Found implementation of procedure is_list_containing_x [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 22:21:18,222 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-06 22:21:18,222 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-06 22:21:18,223 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-06 22:21:18,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-06 22:21:18,223 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-06 22:21:18,223 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-06 22:21:18,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 22:21:18,223 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 22:21:18,323 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 22:21:18,325 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 22:21:18,595 INFO L? ?]: Removed 39 outVars from TransFormulas that were not future-live. [2024-11-06 22:21:18,596 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 22:21:18,607 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 22:21:18,607 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-06 22:21:18,607 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:21:18 BoogieIcfgContainer [2024-11-06 22:21:18,608 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 22:21:18,610 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 22:21:18,610 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 22:21:18,615 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 22:21:18,615 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 10:21:17" (1/3) ... [2024-11-06 22:21:18,618 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41001042 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:21:18, skipping insertion in model container [2024-11-06 22:21:18,618 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 10:21:18" (2/3) ... [2024-11-06 22:21:18,618 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41001042 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 10:21:18, skipping insertion in model container [2024-11-06 22:21:18,618 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 10:21:18" (3/3) ... [2024-11-06 22:21:18,620 INFO L112 eAbstractionObserver]: Analyzing ICFG dancing.i [2024-11-06 22:21:18,634 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 22:21:18,634 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 22:21:18,682 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 22:21:18,695 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;@504c3091, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 22:21:18,696 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 22:21:18,700 INFO L276 IsEmpty]: Start isEmpty. Operand has 43 states, 33 states have (on average 1.4242424242424243) internal successors, (47), 34 states have internal predecessors, (47), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-06 22:21:18,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-06 22:21:18,705 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:18,705 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:21:18,705 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:18,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:18,708 INFO L85 PathProgramCache]: Analyzing trace with hash 329443655, now seen corresponding path program 1 times [2024-11-06 22:21:18,714 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:18,714 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [290835939] [2024-11-06 22:21:18,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:18,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:18,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:18,890 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:18,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:18,913 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-06 22:21:18,914 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:18,914 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [290835939] [2024-11-06 22:21:18,915 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [290835939] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:18,915 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:18,915 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-06 22:21:18,916 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1756300648] [2024-11-06 22:21:18,917 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:18,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-06 22:21:18,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:18,940 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-06 22:21:18,941 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 22:21:18,944 INFO L87 Difference]: Start difference. First operand has 43 states, 33 states have (on average 1.4242424242424243) internal successors, (47), 34 states have internal predecessors, (47), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 22:21:18,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:18,963 INFO L93 Difference]: Finished difference Result 79 states and 109 transitions. [2024-11-06 22:21:18,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-06 22:21:18,966 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2024-11-06 22:21:18,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:18,971 INFO L225 Difference]: With dead ends: 79 [2024-11-06 22:21:18,972 INFO L226 Difference]: Without dead ends: 39 [2024-11-06 22:21:18,974 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 4 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:21:18,978 INFO L432 NwaCegarLoop]: 56 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, 56 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:21:18,979 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:21:18,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2024-11-06 22:21:19,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2024-11-06 22:21:19,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 30 states have (on average 1.3666666666666667) internal successors, (41), 31 states have internal predecessors, (41), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-06 22:21:19,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 52 transitions. [2024-11-06 22:21:19,007 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 52 transitions. Word has length 20 [2024-11-06 22:21:19,008 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:19,008 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 52 transitions. [2024-11-06 22:21:19,008 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 22:21:19,008 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 52 transitions. [2024-11-06 22:21:19,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-06 22:21:19,009 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:19,009 INFO L215 NwaCegarLoop]: trace histogram [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:21:19,010 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-06 22:21:19,010 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:19,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:19,011 INFO L85 PathProgramCache]: Analyzing trace with hash -654440058, now seen corresponding path program 1 times [2024-11-06 22:21:19,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:19,011 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615000976] [2024-11-06 22:21:19,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:19,011 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:19,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,244 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-06 22:21:19,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,253 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-06 22:21:19,256 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:19,257 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615000976] [2024-11-06 22:21:19,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1615000976] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:19,257 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:19,258 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:21:19,258 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [647961667] [2024-11-06 22:21:19,258 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:19,259 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:21:19,259 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:19,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:21:19,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:21:19,261 INFO L87 Difference]: Start difference. First operand 39 states and 52 transitions. Second operand has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 22:21:19,322 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:19,322 INFO L93 Difference]: Finished difference Result 47 states and 60 transitions. [2024-11-06 22:21:19,323 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:21:19,324 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 21 [2024-11-06 22:21:19,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:19,325 INFO L225 Difference]: With dead ends: 47 [2024-11-06 22:21:19,325 INFO L226 Difference]: Without dead ends: 45 [2024-11-06 22:21:19,325 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 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:21:19,326 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 3 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:19,326 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 189 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:21:19,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-06 22:21:19,334 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2024-11-06 22:21:19,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 33 states have (on average 1.3333333333333333) internal successors, (44), 35 states have internal predecessors, (44), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-06 22:21:19,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 57 transitions. [2024-11-06 22:21:19,337 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 57 transitions. Word has length 21 [2024-11-06 22:21:19,338 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:19,338 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 57 transitions. [2024-11-06 22:21:19,339 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-06 22:21:19,339 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 57 transitions. [2024-11-06 22:21:19,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-06 22:21:19,341 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:19,341 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:21:19,341 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-06 22:21:19,341 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:19,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:19,342 INFO L85 PathProgramCache]: Analyzing trace with hash -698021828, now seen corresponding path program 1 times [2024-11-06 22:21:19,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:19,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1483165819] [2024-11-06 22:21:19,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:19,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:19,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,498 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-06 22:21:19,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,510 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-06 22:21:19,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,515 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:21:19,515 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:19,516 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1483165819] [2024-11-06 22:21:19,516 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1483165819] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:19,516 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:19,516 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-06 22:21:19,516 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2126896455] [2024-11-06 22:21:19,516 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:19,516 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-06 22:21:19,517 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:19,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-06 22:21:19,520 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 22:21:19,520 INFO L87 Difference]: Start difference. First operand 44 states and 57 transitions. Second operand has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-06 22:21:19,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:19,572 INFO L93 Difference]: Finished difference Result 90 states and 120 transitions. [2024-11-06 22:21:19,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:21:19,573 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 27 [2024-11-06 22:21:19,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:19,574 INFO L225 Difference]: With dead ends: 90 [2024-11-06 22:21:19,576 INFO L226 Difference]: Without dead ends: 67 [2024-11-06 22:21:19,577 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:21:19,577 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 17 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:19,578 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 142 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:21:19,580 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-06 22:21:19,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 58. [2024-11-06 22:21:19,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 46 states have (on average 1.3478260869565217) internal successors, (62), 48 states have internal predecessors, (62), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-06 22:21:19,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 77 transitions. [2024-11-06 22:21:19,590 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 77 transitions. Word has length 27 [2024-11-06 22:21:19,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:19,591 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 77 transitions. [2024-11-06 22:21:19,591 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-06 22:21:19,591 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 77 transitions. [2024-11-06 22:21:19,592 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-11-06 22:21:19,592 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:19,592 INFO L215 NwaCegarLoop]: trace histogram [2, 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:21:19,593 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-06 22:21:19,593 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:19,593 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:19,593 INFO L85 PathProgramCache]: Analyzing trace with hash -1050140346, now seen corresponding path program 1 times [2024-11-06 22:21:19,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:19,593 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366850712] [2024-11-06 22:21:19,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:19,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:19,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,791 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-06 22:21:19,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,825 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-06 22:21:19,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,831 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-06 22:21:19,831 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:19,831 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1366850712] [2024-11-06 22:21:19,831 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1366850712] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:21:19,831 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625766579] [2024-11-06 22:21:19,832 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:19,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:19,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:21:19,835 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:21:19,836 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:21:19,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:19,985 INFO L255 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-06 22:21:19,990 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:21:20,125 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-06 22:21:20,126 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:21:20,316 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-06 22:21:20,318 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625766579] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:21:20,318 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:21:20,318 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 16 [2024-11-06 22:21:20,318 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [539593237] [2024-11-06 22:21:20,319 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:21:20,319 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-06 22:21:20,319 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:20,320 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-06 22:21:20,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2024-11-06 22:21:20,321 INFO L87 Difference]: Start difference. First operand 58 states and 77 transitions. Second operand has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-06 22:21:20,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:20,708 INFO L93 Difference]: Finished difference Result 107 states and 149 transitions. [2024-11-06 22:21:20,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 22:21:20,708 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) Word has length 32 [2024-11-06 22:21:20,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:20,711 INFO L225 Difference]: With dead ends: 107 [2024-11-06 22:21:20,711 INFO L226 Difference]: Without dead ends: 71 [2024-11-06 22:21:20,712 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=301, Unknown=0, NotChecked=0, Total=380 [2024-11-06 22:21:20,712 INFO L432 NwaCegarLoop]: 66 mSDtfsCounter, 81 mSDsluCounter, 455 mSDsCounter, 0 mSdLazyCounter, 276 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 521 SdHoareTripleChecker+Invalid, 301 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 276 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:20,713 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [81 Valid, 521 Invalid, 301 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 276 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-06 22:21:20,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-06 22:21:20,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 67. [2024-11-06 22:21:20,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 52 states have (on average 1.3461538461538463) internal successors, (70), 56 states have internal predecessors, (70), 10 states have call successors, (10), 3 states have call predecessors, (10), 4 states have return successors, (12), 7 states have call predecessors, (12), 9 states have call successors, (12) [2024-11-06 22:21:20,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 92 transitions. [2024-11-06 22:21:20,728 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 92 transitions. Word has length 32 [2024-11-06 22:21:20,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:20,728 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 92 transitions. [2024-11-06 22:21:20,729 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.1875) internal successors, (51), 16 states have internal predecessors, (51), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2024-11-06 22:21:20,729 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 92 transitions. [2024-11-06 22:21:20,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-06 22:21:20,731 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:20,732 INFO L215 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1] [2024-11-06 22:21:20,751 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-06 22:21:20,932 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:20,933 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:20,933 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:20,933 INFO L85 PathProgramCache]: Analyzing trace with hash 94816722, now seen corresponding path program 1 times [2024-11-06 22:21:20,933 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:20,933 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1216827602] [2024-11-06 22:21:20,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:20,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:20,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,120 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-06 22:21:21,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,125 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-06 22:21:21,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,163 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-06 22:21:21,163 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:21,163 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1216827602] [2024-11-06 22:21:21,163 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1216827602] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:21,163 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:21,163 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-06 22:21:21,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [767831744] [2024-11-06 22:21:21,164 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:21,164 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-06 22:21:21,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:21,164 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-06 22:21:21,164 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-06 22:21:21,164 INFO L87 Difference]: Start difference. First operand 67 states and 92 transitions. Second operand has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:21:21,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:21,218 INFO L93 Difference]: Finished difference Result 78 states and 108 transitions. [2024-11-06 22:21:21,218 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-06 22:21:21,218 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 34 [2024-11-06 22:21:21,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:21,219 INFO L225 Difference]: With dead ends: 78 [2024-11-06 22:21:21,220 INFO L226 Difference]: Without dead ends: 76 [2024-11-06 22:21:21,220 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:21:21,221 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 3 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:21,221 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 300 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:21:21,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-06 22:21:21,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2024-11-06 22:21:21,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 57 states have (on average 1.3157894736842106) internal successors, (75), 62 states have internal predecessors, (75), 11 states have call successors, (11), 4 states have call predecessors, (11), 6 states have return successors, (19), 8 states have call predecessors, (19), 10 states have call successors, (19) [2024-11-06 22:21:21,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 105 transitions. [2024-11-06 22:21:21,231 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 105 transitions. Word has length 34 [2024-11-06 22:21:21,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:21,231 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 105 transitions. [2024-11-06 22:21:21,232 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.333333333333333) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-06 22:21:21,232 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 105 transitions. [2024-11-06 22:21:21,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-06 22:21:21,233 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:21,233 INFO L215 NwaCegarLoop]: trace histogram [2, 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:21:21,233 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-06 22:21:21,233 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:21,234 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:21,234 INFO L85 PathProgramCache]: Analyzing trace with hash -1911567681, now seen corresponding path program 1 times [2024-11-06 22:21:21,234 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:21,234 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [749644829] [2024-11-06 22:21:21,234 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:21,234 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:21,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,859 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-06 22:21:21,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,871 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-06 22:21:21,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,877 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-06 22:21:21,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:21,883 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:21:21,884 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:21,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [749644829] [2024-11-06 22:21:21,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [749644829] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:21,884 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:21,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-06 22:21:21,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1131862585] [2024-11-06 22:21:21,884 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:21,884 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:21:21,884 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:21,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:21:21,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:21:21,885 INFO L87 Difference]: Start difference. First operand 75 states and 105 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-06 22:21:22,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:22,051 INFO L93 Difference]: Finished difference Result 126 states and 175 transitions. [2024-11-06 22:21:22,052 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-06 22:21:22,052 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 36 [2024-11-06 22:21:22,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:22,054 INFO L225 Difference]: With dead ends: 126 [2024-11-06 22:21:22,056 INFO L226 Difference]: Without dead ends: 95 [2024-11-06 22:21:22,057 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2024-11-06 22:21:22,057 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 19 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 170 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:22,057 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 170 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:21:22,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-06 22:21:22,076 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 85. [2024-11-06 22:21:22,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 66 states have (on average 1.3181818181818181) internal successors, (87), 71 states have internal predecessors, (87), 12 states have call successors, (12), 4 states have call predecessors, (12), 6 states have return successors, (22), 9 states have call predecessors, (22), 11 states have call successors, (22) [2024-11-06 22:21:22,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 121 transitions. [2024-11-06 22:21:22,082 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 121 transitions. Word has length 36 [2024-11-06 22:21:22,082 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:22,082 INFO L471 AbstractCegarLoop]: Abstraction has 85 states and 121 transitions. [2024-11-06 22:21:22,082 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-06 22:21:22,082 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 121 transitions. [2024-11-06 22:21:22,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-06 22:21:22,083 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:22,084 INFO L215 NwaCegarLoop]: trace histogram [2, 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:21:22,084 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-06 22:21:22,084 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:22,084 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:22,084 INFO L85 PathProgramCache]: Analyzing trace with hash -1692712963, now seen corresponding path program 1 times [2024-11-06 22:21:22,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:22,084 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [255704808] [2024-11-06 22:21:22,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:22,084 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:22,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,208 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-06 22:21:22,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,212 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-06 22:21:22,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,215 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-06 22:21:22,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,239 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-06 22:21:22,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:22,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [255704808] [2024-11-06 22:21:22,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [255704808] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:22,239 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:22,240 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-06 22:21:22,240 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1750656259] [2024-11-06 22:21:22,240 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:22,240 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 22:21:22,240 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:22,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 22:21:22,241 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-06 22:21:22,241 INFO L87 Difference]: Start difference. First operand 85 states and 121 transitions. Second operand has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-06 22:21:22,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:22,281 INFO L93 Difference]: Finished difference Result 92 states and 127 transitions. [2024-11-06 22:21:22,281 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:21:22,281 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2024-11-06 22:21:22,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:22,282 INFO L225 Difference]: With dead ends: 92 [2024-11-06 22:21:22,282 INFO L226 Difference]: Without dead ends: 85 [2024-11-06 22:21:22,283 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-06 22:21:22,283 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 3 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:22,283 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 254 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 22:21:22,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2024-11-06 22:21:22,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 73. [2024-11-06 22:21:22,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 58 states have (on average 1.3275862068965518) internal successors, (77), 61 states have internal predecessors, (77), 9 states have call successors, (9), 3 states have call predecessors, (9), 5 states have return successors, (17), 8 states have call predecessors, (17), 8 states have call successors, (17) [2024-11-06 22:21:22,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 103 transitions. [2024-11-06 22:21:22,293 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 103 transitions. Word has length 36 [2024-11-06 22:21:22,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:22,293 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 103 transitions. [2024-11-06 22:21:22,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.6) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-06 22:21:22,294 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 103 transitions. [2024-11-06 22:21:22,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-06 22:21:22,295 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:22,295 INFO L215 NwaCegarLoop]: trace histogram [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, 1, 1, 1] [2024-11-06 22:21:22,295 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-06 22:21:22,295 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:22,296 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:22,296 INFO L85 PathProgramCache]: Analyzing trace with hash 1295305490, now seen corresponding path program 1 times [2024-11-06 22:21:22,296 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:22,296 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [258325649] [2024-11-06 22:21:22,296 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:22,296 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:22,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,403 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-06 22:21:22,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,408 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-06 22:21:22,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-06 22:21:22,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,465 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-06 22:21:22,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:22,465 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [258325649] [2024-11-06 22:21:22,465 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [258325649] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 22:21:22,465 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 22:21:22,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-06 22:21:22,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [239398146] [2024-11-06 22:21:22,466 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 22:21:22,469 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-06 22:21:22,470 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:22,470 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-06 22:21:22,470 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-06 22:21:22,470 INFO L87 Difference]: Start difference. First operand 73 states and 103 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-06 22:21:22,558 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:22,558 INFO L93 Difference]: Finished difference Result 123 states and 166 transitions. [2024-11-06 22:21:22,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 22:21:22,559 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 37 [2024-11-06 22:21:22,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:22,561 INFO L225 Difference]: With dead ends: 123 [2024-11-06 22:21:22,561 INFO L226 Difference]: Without dead ends: 57 [2024-11-06 22:21:22,561 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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:21:22,562 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 14 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:22,562 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 163 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-06 22:21:22,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2024-11-06 22:21:22,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 54. [2024-11-06 22:21:22,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 44 states have internal predecessors, (53), 7 states have call successors, (7), 3 states have call predecessors, (7), 5 states have return successors, (11), 6 states have call predecessors, (11), 6 states have call successors, (11) [2024-11-06 22:21:22,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 71 transitions. [2024-11-06 22:21:22,577 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 71 transitions. Word has length 37 [2024-11-06 22:21:22,577 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:22,577 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 71 transitions. [2024-11-06 22:21:22,577 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-06 22:21:22,577 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 71 transitions. [2024-11-06 22:21:22,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-06 22:21:22,578 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:22,579 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:21:22,579 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-06 22:21:22,579 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:22,580 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:22,580 INFO L85 PathProgramCache]: Analyzing trace with hash 569979573, now seen corresponding path program 1 times [2024-11-06 22:21:22,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:22,580 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [481006090] [2024-11-06 22:21:22,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:22,580 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:22,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,747 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-06 22:21:22,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-11-06 22:21:22,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,772 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:22,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,776 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-06 22:21:22,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:22,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [481006090] [2024-11-06 22:21:22,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [481006090] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:21:22,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [159905854] [2024-11-06 22:21:22,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:22,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:22,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:21:22,780 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:21:22,782 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:21:22,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:22,914 INFO L255 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 51 conjuncts are in the unsatisfiable core [2024-11-06 22:21:22,917 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:21:22,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-06 22:21:22,996 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:22,998 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 18 [2024-11-06 22:21:23,012 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-06 22:21:23,020 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:23,021 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 13 [2024-11-06 22:21:23,408 INFO L349 Elim1Store]: treesize reduction 12, result has 77.4 percent of original size [2024-11-06 22:21:23,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 37 treesize of output 57 [2024-11-06 22:21:23,423 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2024-11-06 22:21:23,424 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 7 [2024-11-06 22:21:23,506 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:21:23,506 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:21:23,565 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 4 [2024-11-06 22:21:23,749 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:23,749 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 31 [2024-11-06 22:21:23,759 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:23,759 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 28 [2024-11-06 22:21:23,771 INFO L349 Elim1Store]: treesize reduction 18, result has 5.3 percent of original size [2024-11-06 22:21:23,772 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 1 [2024-11-06 22:21:23,807 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-06 22:21:23,808 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [159905854] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:21:23,808 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:21:23,808 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 9, 7] total 16 [2024-11-06 22:21:23,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2044089202] [2024-11-06 22:21:23,808 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:21:23,809 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-06 22:21:23,810 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:23,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-06 22:21:23,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=202, Unknown=0, NotChecked=0, Total=240 [2024-11-06 22:21:23,811 INFO L87 Difference]: Start difference. First operand 54 states and 71 transitions. Second operand has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-06 22:21:24,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:24,617 INFO L93 Difference]: Finished difference Result 162 states and 215 transitions. [2024-11-06 22:21:24,617 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-06 22:21:24,618 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 40 [2024-11-06 22:21:24,618 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:24,619 INFO L225 Difference]: With dead ends: 162 [2024-11-06 22:21:24,619 INFO L226 Difference]: Without dead ends: 119 [2024-11-06 22:21:24,620 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=156, Invalid=656, Unknown=0, NotChecked=0, Total=812 [2024-11-06 22:21:24,620 INFO L432 NwaCegarLoop]: 67 mSDtfsCounter, 135 mSDsluCounter, 567 mSDsCounter, 0 mSdLazyCounter, 371 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 634 SdHoareTripleChecker+Invalid, 401 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 371 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:24,621 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 634 Invalid, 401 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 371 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-06 22:21:24,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-11-06 22:21:24,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 98. [2024-11-06 22:21:24,643 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 73 states have (on average 1.2876712328767124) internal successors, (94), 79 states have internal predecessors, (94), 14 states have call successors, (14), 6 states have call predecessors, (14), 10 states have return successors, (20), 12 states have call predecessors, (20), 12 states have call successors, (20) [2024-11-06 22:21:24,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 128 transitions. [2024-11-06 22:21:24,645 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 128 transitions. Word has length 40 [2024-11-06 22:21:24,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:24,646 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 128 transitions. [2024-11-06 22:21:24,646 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.875) internal successors, (62), 15 states have internal predecessors, (62), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-06 22:21:24,646 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 128 transitions. [2024-11-06 22:21:24,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-06 22:21:24,648 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:24,648 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:21:24,668 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:21:24,854 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:24,855 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:24,855 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:24,855 INFO L85 PathProgramCache]: Analyzing trace with hash -1413843308, now seen corresponding path program 1 times [2024-11-06 22:21:24,855 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:24,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566421133] [2024-11-06 22:21:24,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:24,855 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:24,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,196 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-06 22:21:25,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,204 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:25,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,207 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-06 22:21:25,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,212 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:25,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,215 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2024-11-06 22:21:25,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:25,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566421133] [2024-11-06 22:21:25,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1566421133] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:21:25,216 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [614663583] [2024-11-06 22:21:25,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:25,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:25,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:21:25,219 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:21:25,221 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:21:25,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:25,350 INFO L255 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-06 22:21:25,353 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:21:25,417 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:25,418 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 25 [2024-11-06 22:21:25,422 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:25,423 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 18 [2024-11-06 22:21:25,948 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 19 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-06 22:21:25,949 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:21:26,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [614663583] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:21:26,025 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 22:21:26,025 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11] total 19 [2024-11-06 22:21:26,026 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1527844629] [2024-11-06 22:21:26,026 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 22:21:26,026 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-06 22:21:26,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:21:26,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-06 22:21:26,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=332, Unknown=0, NotChecked=0, Total=380 [2024-11-06 22:21:26,027 INFO L87 Difference]: Start difference. First operand 98 states and 128 transitions. Second operand has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-06 22:21:27,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 22:21:27,208 INFO L93 Difference]: Finished difference Result 182 states and 232 transitions. [2024-11-06 22:21:27,209 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-06 22:21:27,210 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 46 [2024-11-06 22:21:27,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 22:21:27,211 INFO L225 Difference]: With dead ends: 182 [2024-11-06 22:21:27,211 INFO L226 Difference]: Without dead ends: 114 [2024-11-06 22:21:27,212 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=222, Invalid=900, Unknown=0, NotChecked=0, Total=1122 [2024-11-06 22:21:27,212 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 124 mSDsluCounter, 505 mSDsCounter, 0 mSdLazyCounter, 485 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 558 SdHoareTripleChecker+Invalid, 519 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 485 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-06 22:21:27,212 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 558 Invalid, 519 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 485 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-06 22:21:27,213 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-11-06 22:21:27,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 72. [2024-11-06 22:21:27,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 55 states have (on average 1.2727272727272727) internal successors, (70), 59 states have internal predecessors, (70), 9 states have call successors, (9), 4 states have call predecessors, (9), 7 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-11-06 22:21:27,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 92 transitions. [2024-11-06 22:21:27,231 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 92 transitions. Word has length 46 [2024-11-06 22:21:27,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 22:21:27,232 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 92 transitions. [2024-11-06 22:21:27,232 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 5 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-06 22:21:27,232 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 92 transitions. [2024-11-06 22:21:27,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-06 22:21:27,233 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 22:21:27,233 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-06 22:21:27,252 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:21:27,434 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:27,434 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 22:21:27,434 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 22:21:27,435 INFO L85 PathProgramCache]: Analyzing trace with hash -596194858, now seen corresponding path program 1 times [2024-11-06 22:21:27,435 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-06 22:21:27,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1210080481] [2024-11-06 22:21:27,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:27,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-06 22:21:27,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,237 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-06 22:21:28,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,255 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:28,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-06 22:21:28,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,358 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-06 22:21:28,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,405 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-06 22:21:28,406 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-06 22:21:28,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1210080481] [2024-11-06 22:21:28,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1210080481] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 22:21:28,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1370106407] [2024-11-06 22:21:28,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 22:21:28,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 22:21:28,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 22:21:28,409 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:21:28,412 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:21:28,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 22:21:28,545 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 101 conjuncts are in the unsatisfiable core [2024-11-06 22:21:28,551 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 22:21:28,645 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2024-11-06 22:21:28,655 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:28,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2024-11-06 22:21:28,671 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2024-11-06 22:21:28,675 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-06 22:21:28,677 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 16 [2024-11-06 22:21:29,311 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-06 22:21:29,311 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 34 treesize of output 31 [2024-11-06 22:21:29,325 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-06 22:21:54,288 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 2 proven. 23 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-06 22:21:54,289 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 22:21:54,406 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-11-06 22:21:54,729 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2024-11-06 22:21:55,248 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:55,248 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 218 treesize of output 237 [2024-11-06 22:21:55,273 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:55,274 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 220 treesize of output 154 [2024-11-06 22:21:55,408 INFO L349 Elim1Store]: treesize reduction 68, result has 48.5 percent of original size [2024-11-06 22:21:55,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 9 case distinctions, treesize of input 774 treesize of output 756 [2024-11-06 22:21:55,447 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 470 treesize of output 445 [2024-11-06 22:21:55,476 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 295 treesize of output 285 [2024-11-06 22:21:55,640 INFO L349 Elim1Store]: treesize reduction 44, result has 70.9 percent of original size [2024-11-06 22:21:55,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 862 treesize of output 882 [2024-11-06 22:21:55,724 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:55,725 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 768 treesize of output 702 [2024-11-06 22:21:55,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 353 treesize of output 321 [2024-11-06 22:21:55,834 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:21:55,834 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 489 treesize of output 477 [2024-11-06 22:21:58,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 326 treesize of output 320 [2024-11-06 22:21:58,828 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 74 [2024-11-06 22:21:59,714 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 900 treesize of output 882 [2024-11-06 22:22:02,805 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-06 22:22:02,811 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:22:02,811 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 326 treesize of output 306 [2024-11-06 22:22:02,838 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:22:02,838 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 287 treesize of output 276 [2024-11-06 22:22:03,119 INFO L349 Elim1Store]: treesize reduction 5, result has 73.7 percent of original size [2024-11-06 22:22:03,120 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 130 treesize of output 122 [2024-11-06 22:22:03,139 INFO L349 Elim1Store]: treesize reduction 9, result has 52.6 percent of original size [2024-11-06 22:22:03,140 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 123 treesize of output 116 [2024-11-06 22:22:03,202 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-06 22:22:03,233 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 22:22:03,233 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 4 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 7 case distinctions, treesize of input 361 treesize of output 359 [2024-11-06 22:22:03,642 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-06 22:22:03,652 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-06 22:22:03,667 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 43 [2024-11-06 22:22:03,682 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 120 treesize of output 100 [2024-11-06 22:22:03,721 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-06 22:22:03,739 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-06 22:22:03,758 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2024-11-06 22:22:03,780 INFO L349 Elim1Store]: treesize reduction 70, result has 1.4 percent of original size [2024-11-06 22:22:03,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 2 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 8 case distinctions, treesize of input 145 treesize of output 1 [2024-11-06 22:22:04,006 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 15 proven. 5 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-06 22:22:04,006 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1370106407] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 22:22:04,006 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 22:22:04,006 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19, 15] total 46 [2024-11-06 22:22:04,006 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [646786543] [2024-11-06 22:22:04,006 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 22:22:04,007 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2024-11-06 22:22:04,007 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-06 22:22:04,007 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2024-11-06 22:22:04,008 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=1901, Unknown=6, NotChecked=0, Total=2070 [2024-11-06 22:22:04,009 INFO L87 Difference]: Start difference. First operand 72 states and 92 transitions. Second operand has 46 states, 42 states have (on average 2.119047619047619) internal successors, (89), 44 states have internal predecessors, (89), 12 states have call successors, (12), 5 states have call predecessors, (12), 8 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-06 22:22:09,489 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:17,580 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:21,585 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:29,666 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:33,674 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:37,681 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:49,738 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 22:22:53,747 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]