./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/array-patterns/array19_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 35987657 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-patterns/array19_pattern.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --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 21ab39d122ec2c6e96fa6b8c9d53d6f966068253a8a3d3ba32389613dd7dc54a --- Real Ultimate output --- This is Ultimate 0.2.2-?-3598765 [2022-07-20 21:45:23,151 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-20 21:45:23,153 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-20 21:45:23,176 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-20 21:45:23,177 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-20 21:45:23,178 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-20 21:45:23,179 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-20 21:45:23,180 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-20 21:45:23,182 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-20 21:45:23,182 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-20 21:45:23,183 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-20 21:45:23,184 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-20 21:45:23,184 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-20 21:45:23,185 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-20 21:45:23,186 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-20 21:45:23,187 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-20 21:45:23,188 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-20 21:45:23,189 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-20 21:45:23,190 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-20 21:45:23,192 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-20 21:45:23,193 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-20 21:45:23,194 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-20 21:45:23,195 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-20 21:45:23,196 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-20 21:45:23,197 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-20 21:45:23,199 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-20 21:45:23,200 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-20 21:45:23,200 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-20 21:45:23,201 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-20 21:45:23,201 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-20 21:45:23,202 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-20 21:45:23,202 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-20 21:45:23,203 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-20 21:45:23,204 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-20 21:45:23,204 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-20 21:45:23,205 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-20 21:45:23,205 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-20 21:45:23,206 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-20 21:45:23,206 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-20 21:45:23,207 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-20 21:45:23,207 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-20 21:45:23,208 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-20 21:45:23,209 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-20 21:45:23,227 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-20 21:45:23,228 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-20 21:45:23,228 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-20 21:45:23,228 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-20 21:45:23,229 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-20 21:45:23,229 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-20 21:45:23,230 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-20 21:45:23,230 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-20 21:45:23,230 INFO L138 SettingsManager]: * Use SBE=true [2022-07-20 21:45:23,231 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-20 21:45:23,231 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-20 21:45:23,231 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-20 21:45:23,232 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-20 21:45:23,232 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-20 21:45:23,232 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-20 21:45:23,232 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-20 21:45:23,232 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-20 21:45:23,233 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-20 21:45:23,233 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-20 21:45:23,233 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-20 21:45:23,234 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-20 21:45:23,234 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-20 21:45:23,234 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-20 21:45:23,234 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-20 21:45:23,235 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-20 21:45:23,235 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-20 21:45:23,235 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-20 21:45:23,235 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-20 21:45:23,236 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-20 21:45:23,236 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-20 21:45:23,236 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-20 21:45:23,236 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-20 21:45:23,237 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-20 21:45:23,237 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> 21ab39d122ec2c6e96fa6b8c9d53d6f966068253a8a3d3ba32389613dd7dc54a [2022-07-20 21:45:23,464 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-20 21:45:23,483 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-20 21:45:23,486 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-20 21:45:23,487 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-20 21:45:23,488 INFO L275 PluginConnector]: CDTParser initialized [2022-07-20 21:45:23,489 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-patterns/array19_pattern.c [2022-07-20 21:45:23,547 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a44595352/5da08154473648f184aecb1ea55beffa/FLAG5c09932db [2022-07-20 21:45:23,926 INFO L306 CDTParser]: Found 1 translation units. [2022-07-20 21:45:23,927 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c [2022-07-20 21:45:23,935 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a44595352/5da08154473648f184aecb1ea55beffa/FLAG5c09932db [2022-07-20 21:45:23,946 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a44595352/5da08154473648f184aecb1ea55beffa [2022-07-20 21:45:23,948 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-20 21:45:23,952 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-20 21:45:23,953 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-20 21:45:23,954 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-20 21:45:23,956 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-20 21:45:23,957 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.07 09:45:23" (1/1) ... [2022-07-20 21:45:23,958 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@695c2dff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:23, skipping insertion in model container [2022-07-20 21:45:23,958 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.07 09:45:23" (1/1) ... [2022-07-20 21:45:23,965 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-20 21:45:23,980 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-20 21:45:24,125 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c[1442,1455] [2022-07-20 21:45:24,161 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-20 21:45:24,168 INFO L203 MainTranslator]: Completed pre-run [2022-07-20 21:45:24,178 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c[1442,1455] [2022-07-20 21:45:24,187 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-20 21:45:24,197 INFO L208 MainTranslator]: Completed translation [2022-07-20 21:45:24,197 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24 WrapperNode [2022-07-20 21:45:24,197 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-20 21:45:24,198 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-20 21:45:24,199 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-20 21:45:24,199 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-20 21:45:24,205 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,211 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,230 INFO L137 Inliner]: procedures = 16, calls = 20, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 102 [2022-07-20 21:45:24,231 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-20 21:45:24,231 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-20 21:45:24,232 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-20 21:45:24,232 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-20 21:45:24,241 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,243 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,246 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,247 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,252 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,257 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,258 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,260 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-20 21:45:24,261 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-20 21:45:24,261 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-20 21:45:24,261 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-20 21:45:24,262 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (1/1) ... [2022-07-20 21:45:24,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-20 21:45:24,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:45:24,293 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-20 21:45:24,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-20 21:45:24,320 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-20 21:45:24,321 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-20 21:45:24,321 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-20 21:45:24,321 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-20 21:45:24,321 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-20 21:45:24,321 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-07-20 21:45:24,322 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-20 21:45:24,322 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-20 21:45:24,322 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-07-20 21:45:24,322 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-20 21:45:24,383 INFO L234 CfgBuilder]: Building ICFG [2022-07-20 21:45:24,385 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-20 21:45:24,562 INFO L275 CfgBuilder]: Performing block encoding [2022-07-20 21:45:24,567 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-20 21:45:24,569 INFO L299 CfgBuilder]: Removed 5 assume(true) statements. [2022-07-20 21:45:24,571 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.07 09:45:24 BoogieIcfgContainer [2022-07-20 21:45:24,571 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-20 21:45:24,585 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-20 21:45:24,585 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-20 21:45:24,588 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-20 21:45:24,589 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.07 09:45:23" (1/3) ... [2022-07-20 21:45:24,589 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d0dcabb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.07 09:45:24, skipping insertion in model container [2022-07-20 21:45:24,590 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:45:24" (2/3) ... [2022-07-20 21:45:24,590 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d0dcabb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.07 09:45:24, skipping insertion in model container [2022-07-20 21:45:24,590 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.07 09:45:24" (3/3) ... [2022-07-20 21:45:24,591 INFO L111 eAbstractionObserver]: Analyzing ICFG array19_pattern.c [2022-07-20 21:45:24,603 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-20 21:45:24,604 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-20 21:45:24,646 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-20 21:45:24,661 INFO L357 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, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@70e74391, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@f0e7196 [2022-07-20 21:45:24,662 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-20 21:45:24,668 INFO L276 IsEmpty]: Start isEmpty. Operand has 33 states, 27 states have (on average 1.5925925925925926) internal successors, (43), 28 states have internal predecessors, (43), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:45:24,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-07-20 21:45:24,678 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:45:24,678 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:45:24,680 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:45:24,690 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:45:24,690 INFO L85 PathProgramCache]: Analyzing trace with hash -2132324569, now seen corresponding path program 1 times [2022-07-20 21:45:24,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-20 21:45:24,700 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1723574773] [2022-07-20 21:45:24,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:24,701 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-20 21:45:24,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:24,854 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-20 21:45:24,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:24,866 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-20 21:45:24,867 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-20 21:45:24,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1723574773] [2022-07-20 21:45:24,868 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1723574773] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:45:24,868 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:45:24,868 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-20 21:45:24,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1946868498] [2022-07-20 21:45:24,870 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:45:24,876 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-20 21:45:24,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-20 21:45:24,904 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-20 21:45:24,905 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-20 21:45:24,907 INFO L87 Difference]: Start difference. First operand has 33 states, 27 states have (on average 1.5925925925925926) internal successors, (43), 28 states have internal predecessors, (43), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-20 21:45:24,929 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:45:24,929 INFO L93 Difference]: Finished difference Result 63 states and 97 transitions. [2022-07-20 21:45:24,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-20 21:45:24,931 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-07-20 21:45:24,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:45:24,939 INFO L225 Difference]: With dead ends: 63 [2022-07-20 21:45:24,939 INFO L226 Difference]: Without dead ends: 29 [2022-07-20 21:45:24,941 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-20 21:45:24,945 INFO L413 NwaCegarLoop]: 41 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, 41 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 [2022-07-20 21:45:24,945 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-20 21:45:24,957 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-07-20 21:45:24,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-07-20 21:45:24,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 24 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:45:24,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 37 transitions. [2022-07-20 21:45:24,974 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 37 transitions. Word has length 15 [2022-07-20 21:45:24,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:45:24,974 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 37 transitions. [2022-07-20 21:45:24,974 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-20 21:45:24,975 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 37 transitions. [2022-07-20 21:45:24,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-07-20 21:45:24,978 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:45:24,978 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:45:24,978 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-20 21:45:24,979 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:45:24,980 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:45:24,980 INFO L85 PathProgramCache]: Analyzing trace with hash 1872922357, now seen corresponding path program 1 times [2022-07-20 21:45:24,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-20 21:45:24,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326392591] [2022-07-20 21:45:24,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:24,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-20 21:45:25,011 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-20 21:45:25,019 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2005305818] [2022-07-20 21:45:25,019 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:25,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:25,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:45:25,027 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-20 21:45:25,038 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-20 21:45:25,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:25,136 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-20 21:45:25,140 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:45:25,231 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-20 21:45:25,232 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:45:25,232 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-20 21:45:25,232 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326392591] [2022-07-20 21:45:25,233 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-20 21:45:25,234 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2005305818] [2022-07-20 21:45:25,236 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2005305818] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:45:25,236 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:45:25,236 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-20 21:45:25,237 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [788999126] [2022-07-20 21:45:25,237 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:45:25,238 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-20 21:45:25,238 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-20 21:45:25,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-20 21:45:25,239 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-20 21:45:25,239 INFO L87 Difference]: Start difference. First operand 29 states and 37 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:25,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:45:25,266 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-07-20 21:45:25,267 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-20 21:45:25,267 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2022-07-20 21:45:25,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:45:25,269 INFO L225 Difference]: With dead ends: 36 [2022-07-20 21:45:25,269 INFO L226 Difference]: Without dead ends: 32 [2022-07-20 21:45:25,269 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-07-20 21:45:25,271 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 12 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:45:25,272 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 84 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-20 21:45:25,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-07-20 21:45:25,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-07-20 21:45:25,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 27 states have internal predecessors, (35), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:45:25,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-07-20 21:45:25,279 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 30 [2022-07-20 21:45:25,280 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:45:25,280 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-07-20 21:45:25,280 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:25,281 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-07-20 21:45:25,281 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-20 21:45:25,281 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:45:25,282 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:45:25,298 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-07-20 21:45:25,482 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:25,483 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:45:25,483 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:45:25,483 INFO L85 PathProgramCache]: Analyzing trace with hash 212512359, now seen corresponding path program 1 times [2022-07-20 21:45:25,483 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-20 21:45:25,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [866022629] [2022-07-20 21:45:25,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:25,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-20 21:45:25,496 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-20 21:45:25,497 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [955604807] [2022-07-20 21:45:25,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:25,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:25,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:45:25,498 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-20 21:45:25,505 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-20 21:45:25,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:25,557 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-20 21:45:25,559 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:45:25,625 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-07-20 21:45:25,626 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:45:25,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-20 21:45:25,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [866022629] [2022-07-20 21:45:25,628 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-20 21:45:25,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [955604807] [2022-07-20 21:45:25,628 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [955604807] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:45:25,628 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:45:25,628 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-20 21:45:25,629 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1172889247] [2022-07-20 21:45:25,629 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:45:25,629 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-20 21:45:25,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-20 21:45:25,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-20 21:45:25,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-07-20 21:45:25,631 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 5 states, 5 states have (on average 5.2) 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, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:25,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:45:25,742 INFO L93 Difference]: Finished difference Result 67 states and 86 transitions. [2022-07-20 21:45:25,742 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-20 21:45:25,742 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) 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, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2022-07-20 21:45:25,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:45:25,743 INFO L225 Difference]: With dead ends: 67 [2022-07-20 21:45:25,743 INFO L226 Difference]: Without dead ends: 42 [2022-07-20 21:45:25,744 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:45:25,745 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 22 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-20 21:45:25,745 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 80 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-20 21:45:25,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-07-20 21:45:25,749 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 33. [2022-07-20 21:45:25,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 28 states have internal predecessors, (36), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:45:25,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2022-07-20 21:45:25,752 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 35 [2022-07-20 21:45:25,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:45:25,752 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2022-07-20 21:45:25,752 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) 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, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:25,752 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2022-07-20 21:45:25,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-07-20 21:45:25,753 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:45:25,753 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:45:25,770 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-20 21:45:25,954 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-07-20 21:45:25,955 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:45:25,955 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:45:25,956 INFO L85 PathProgramCache]: Analyzing trace with hash -654332553, now seen corresponding path program 1 times [2022-07-20 21:45:25,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-20 21:45:25,956 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1491348641] [2022-07-20 21:45:25,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:25,959 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-20 21:45:25,980 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-20 21:45:25,981 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2125860560] [2022-07-20 21:45:25,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:25,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:25,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:45:25,992 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-20 21:45:26,013 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-20 21:45:26,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:26,058 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-20 21:45:26,067 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:45:26,100 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-20 21:45:26,100 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:45:26,101 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-20 21:45:26,101 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1491348641] [2022-07-20 21:45:26,101 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-20 21:45:26,101 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2125860560] [2022-07-20 21:45:26,101 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2125860560] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:45:26,102 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:45:26,102 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-20 21:45:26,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [422676783] [2022-07-20 21:45:26,102 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:45:26,102 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-20 21:45:26,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-20 21:45:26,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-20 21:45:26,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-20 21:45:26,103 INFO L87 Difference]: Start difference. First operand 33 states and 42 transitions. Second operand has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:26,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:45:26,147 INFO L93 Difference]: Finished difference Result 64 states and 83 transitions. [2022-07-20 21:45:26,147 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-20 21:45:26,147 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 38 [2022-07-20 21:45:26,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:45:26,149 INFO L225 Difference]: With dead ends: 64 [2022-07-20 21:45:26,149 INFO L226 Difference]: Without dead ends: 36 [2022-07-20 21:45:26,150 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-07-20 21:45:26,153 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 26 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:45:26,154 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 51 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-20 21:45:26,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-07-20 21:45:26,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 33. [2022-07-20 21:45:26,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 28 states have (on average 1.25) internal successors, (35), 28 states have internal predecessors, (35), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:45:26,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2022-07-20 21:45:26,168 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 38 [2022-07-20 21:45:26,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:45:26,171 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2022-07-20 21:45:26,172 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:45:26,172 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2022-07-20 21:45:26,174 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-07-20 21:45:26,174 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:45:26,175 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:45:26,204 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-20 21:45:26,388 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:26,389 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:45:26,389 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:45:26,390 INFO L85 PathProgramCache]: Analyzing trace with hash 579061941, now seen corresponding path program 1 times [2022-07-20 21:45:26,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-20 21:45:26,390 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2011426054] [2022-07-20 21:45:26,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:26,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-20 21:45:26,405 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-20 21:45:26,409 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1636554097] [2022-07-20 21:45:26,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:45:26,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:45:26,409 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:45:26,411 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-20 21:45:26,412 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-20 21:45:26,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:45:26,498 INFO L263 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 45 conjunts are in the unsatisfiable core [2022-07-20 21:45:26,502 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:45:26,589 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 45 treesize of output 40 [2022-07-20 21:45:26,596 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2022-07-20 21:45:26,610 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2022-07-20 21:45:27,126 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 316 treesize of output 297 [2022-07-20 21:45:27,902 INFO L356 Elim1Store]: treesize reduction 428, result has 1.2 percent of original size [2022-07-20 21:45:27,903 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 8 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 9 new quantified variables, introduced 8 case distinctions, treesize of input 308 treesize of output 2651 [2022-07-20 21:45:29,696 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,712 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,731 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:29,763 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,782 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,797 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,811 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,821 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:29,831 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,835 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:29,857 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,885 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,893 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,900 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,908 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,950 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,955 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:29,990 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:29,992 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:29,998 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,011 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,022 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,046 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,047 INFO L244 Elim1Store]: Index analysis took 362 ms [2022-07-20 21:45:30,066 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,078 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:30,080 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 7 stores, 1 select indices, 1 select index equivalence classes, 11 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 604 treesize of output 3427 [2022-07-20 21:45:32,170 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 178 treesize of output 167 [2022-07-20 21:45:32,290 INFO L356 Elim1Store]: treesize reduction 512, result has 4.7 percent of original size [2022-07-20 21:45:32,291 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 4 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 170 treesize of output 679 [2022-07-20 21:45:32,526 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:32,528 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:32,532 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:32,534 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:32,536 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:32,545 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:32,562 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:45:32,564 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:32,576 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:32,590 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:45:32,592 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 3 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 276 treesize of output 493 [2022-07-20 21:45:33,973 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 1518 treesize of output 1492 [2022-07-20 21:46:02,361 WARN L233 SmtUtils]: Spent 28.32s on a formula simplification. DAG size of input: 524 DAG size of output: 80 (called from [L 353] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2022-07-20 21:46:02,362 INFO L356 Elim1Store]: treesize reduction 17846, result has 1.8 percent of original size [2022-07-20 21:46:02,365 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 14 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 17 new quantified variables, introduced 77 case distinctions, treesize of input 31679315 treesize of output 7724287 [2022-07-20 21:46:19,643 WARN L233 SmtUtils]: Spent 17.27s on a formula simplification. DAG size of input: 2743 DAG size of output: 2743 (called from [L 927] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-07-20 21:46:22,588 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:22,632 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:22,676 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:22,817 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:22,908 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:22,986 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:22,989 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:23,079 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,201 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,311 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,449 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,489 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:23,533 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:23,667 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,800 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:23,930 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,040 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,145 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,248 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,348 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,489 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,592 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:24,725 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:25,010 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:25,274 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-20 21:46:25,457 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,607 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,667 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,812 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,830 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,840 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:25,923 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,000 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,121 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,233 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,276 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,314 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,336 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,394 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,429 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,461 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,609 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,642 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,806 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:26,807 INFO L244 Elim1Store]: Index analysis took 4306 ms [2022-07-20 21:46:26,814 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-20 21:46:26,815 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2011426054] [2022-07-20 21:46:26,815 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-20 21:46:26,815 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1636554097] [2022-07-20 21:46:26,815 WARN L319 FreeRefinementEngine]: Global settings require throwing the following exception [2022-07-20 21:46:26,836 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-20 21:46:27,016 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-20 21:46:27,016 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.ClassCastException: class de.uni_freiburg.informatik.ultimate.logic.ConstantTerm cannot be cast to class de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm (de.uni_freiburg.informatik.ultimate.logic.ConstantTerm and de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm are in unnamed module of loader org.eclipse.osgi.internal.loader.EquinoxClassLoader @54e81b21) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.arrays.MultiDimensionalSelect.(MultiDimensionalSelect.java:103) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.arrays.ArrayIndexEqualityManager.constructNestedStoreUpdateConstraintForOnePosition(ArrayIndexEqualityManager.java:415) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.arrays.ArrayIndexEqualityManager.constructNestedStoreUpdateConstraint(ArrayIndexEqualityManager.java:449) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.constructWriteConstraints2(Elim1Store.java:975) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1(Elim1Store.java:314) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:427) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:190) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne3(DualJunctionSaa.java:172) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne2(DualJunctionSaa.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne1(DualJunctionSaa.java:140) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne0(DualJunctionSaa.java:124) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne(DualJunctionSaa.java:108) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryExhaustivelyToEliminate(DualJunctionSaa.java:93) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:88) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToEliminateOne(QuantifierPusher.java:764) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyNewEliminationTechniquesExhaustively(QuantifierPusher.java:725) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyDualJunctionEliminationTechniques(QuantifierPusher.java:643) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:335) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:176) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:65) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:61) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:265) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:251) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminate(PartialQuantifierElimination.java:90) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer$QuantifierEliminationPostprocessor.postprocess(IterativePredicateTransformer.java:238) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:420) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeStrongestPostconditionSequence(IterativePredicateTransformer.java:199) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:299) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:185) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:163) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:108) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:121) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:248) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:431) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:366) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:348) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:409) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:300) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:260) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:173) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:152) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2022-07-20 21:46:27,020 INFO L158 Benchmark]: Toolchain (without parser) took 63068.14ms. Allocated memory was 94.4MB in the beginning and 343.9MB in the end (delta: 249.6MB). Free memory was 63.3MB in the beginning and 258.9MB in the end (delta: -195.6MB). Peak memory consumption was 201.0MB. Max. memory is 16.1GB. [2022-07-20 21:46:27,021 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 94.4MB. Free memory is still 51.4MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-20 21:46:27,021 INFO L158 Benchmark]: CACSL2BoogieTranslator took 244.47ms. Allocated memory was 94.4MB in the beginning and 113.2MB in the end (delta: 18.9MB). Free memory was 63.1MB in the beginning and 88.8MB in the end (delta: -25.7MB). Peak memory consumption was 6.3MB. Max. memory is 16.1GB. [2022-07-20 21:46:27,022 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.45ms. Allocated memory is still 113.2MB. Free memory was 88.8MB in the beginning and 87.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-07-20 21:46:27,022 INFO L158 Benchmark]: Boogie Preprocessor took 28.56ms. Allocated memory is still 113.2MB. Free memory was 87.1MB in the beginning and 85.7MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-20 21:46:27,022 INFO L158 Benchmark]: RCFGBuilder took 310.58ms. Allocated memory is still 113.2MB. Free memory was 85.7MB in the beginning and 72.8MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2022-07-20 21:46:27,026 INFO L158 Benchmark]: TraceAbstraction took 62435.43ms. Allocated memory was 113.2MB in the beginning and 343.9MB in the end (delta: 230.7MB). Free memory was 72.4MB in the beginning and 258.9MB in the end (delta: -186.5MB). Peak memory consumption was 191.5MB. Max. memory is 16.1GB. [2022-07-20 21:46:27,029 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21ms. Allocated memory is still 94.4MB. Free memory is still 51.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 244.47ms. Allocated memory was 94.4MB in the beginning and 113.2MB in the end (delta: 18.9MB). Free memory was 63.1MB in the beginning and 88.8MB in the end (delta: -25.7MB). Peak memory consumption was 6.3MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.45ms. Allocated memory is still 113.2MB. Free memory was 88.8MB in the beginning and 87.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 28.56ms. Allocated memory is still 113.2MB. Free memory was 87.1MB in the beginning and 85.7MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 310.58ms. Allocated memory is still 113.2MB. Free memory was 85.7MB in the beginning and 72.8MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 62435.43ms. Allocated memory was 113.2MB in the beginning and 343.9MB in the end (delta: 230.7MB). Free memory was 72.4MB in the beginning and 258.9MB in the end (delta: -186.5MB). Peak memory consumption was 191.5MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: ClassCastException: class de.uni_freiburg.informatik.ultimate.logic.ConstantTerm cannot be cast to class de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm (de.uni_freiburg.informatik.ultimate.logic.ConstantTerm and de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm are in unnamed module of loader org.eclipse.osgi.internal.loader.EquinoxClassLoader @54e81b21) de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: ClassCastException: class de.uni_freiburg.informatik.ultimate.logic.ConstantTerm cannot be cast to class de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm (de.uni_freiburg.informatik.ultimate.logic.ConstantTerm and de.uni_freiburg.informatik.ultimate.logic.ApplicationTerm are in unnamed module of loader org.eclipse.osgi.internal.loader.EquinoxClassLoader @54e81b21): de.uni_freiburg.informatik.ultimate.lib.smtlibutils.arrays.MultiDimensionalSelect.(MultiDimensionalSelect.java:103) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2022-07-20 21:46:27,087 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/array-patterns/array19_pattern.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --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 21ab39d122ec2c6e96fa6b8c9d53d6f966068253a8a3d3ba32389613dd7dc54a --- Real Ultimate output --- This is Ultimate 0.2.2-?-3598765 [2022-07-20 21:46:28,905 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-20 21:46:28,908 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-20 21:46:28,957 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-20 21:46:28,957 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-20 21:46:28,959 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-20 21:46:28,962 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-20 21:46:28,965 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-20 21:46:28,967 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-20 21:46:28,971 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-20 21:46:28,972 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-20 21:46:28,974 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-20 21:46:28,975 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-20 21:46:28,976 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-20 21:46:28,977 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-20 21:46:28,982 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-20 21:46:28,983 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-20 21:46:28,985 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-20 21:46:28,986 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-20 21:46:28,991 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-20 21:46:28,993 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-20 21:46:28,993 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-20 21:46:28,995 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-20 21:46:28,996 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-20 21:46:28,997 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-20 21:46:29,004 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-20 21:46:29,004 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-20 21:46:29,004 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-20 21:46:29,005 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-20 21:46:29,006 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-20 21:46:29,007 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-20 21:46:29,007 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-20 21:46:29,009 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-20 21:46:29,009 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-20 21:46:29,011 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-20 21:46:29,011 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-20 21:46:29,012 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-20 21:46:29,012 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-20 21:46:29,012 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-20 21:46:29,013 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-20 21:46:29,013 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-20 21:46:29,014 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-20 21:46:29,020 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2022-07-20 21:46:29,052 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-20 21:46:29,052 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-20 21:46:29,053 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-20 21:46:29,053 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-20 21:46:29,053 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-20 21:46:29,054 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-20 21:46:29,054 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-20 21:46:29,055 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-20 21:46:29,055 INFO L138 SettingsManager]: * Use SBE=true [2022-07-20 21:46:29,055 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-20 21:46:29,056 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-20 21:46:29,056 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-20 21:46:29,056 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-20 21:46:29,056 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-20 21:46:29,056 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-20 21:46:29,057 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-20 21:46:29,057 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2022-07-20 21:46:29,057 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2022-07-20 21:46:29,057 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2022-07-20 21:46:29,057 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-20 21:46:29,058 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-20 21:46:29,058 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-20 21:46:29,058 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-20 21:46:29,058 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-20 21:46:29,058 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-20 21:46:29,059 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-20 21:46:29,059 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-20 21:46:29,059 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-20 21:46:29,059 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-20 21:46:29,059 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-20 21:46:29,060 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2022-07-20 21:46:29,060 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2022-07-20 21:46:29,060 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-20 21:46:29,060 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-20 21:46:29,060 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-20 21:46:29,061 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-07-20 21:46:29,061 INFO L138 SettingsManager]: * Logic for external solver=AUFBV WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> 21ab39d122ec2c6e96fa6b8c9d53d6f966068253a8a3d3ba32389613dd7dc54a [2022-07-20 21:46:29,384 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-20 21:46:29,414 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-20 21:46:29,416 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-20 21:46:29,417 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-20 21:46:29,418 INFO L275 PluginConnector]: CDTParser initialized [2022-07-20 21:46:29,419 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/array-patterns/array19_pattern.c [2022-07-20 21:46:29,475 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4a194c513/23a955c2402044419cb583f6f0c095ee/FLAGfc7ecf854 [2022-07-20 21:46:29,853 INFO L306 CDTParser]: Found 1 translation units. [2022-07-20 21:46:29,854 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c [2022-07-20 21:46:29,861 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4a194c513/23a955c2402044419cb583f6f0c095ee/FLAGfc7ecf854 [2022-07-20 21:46:30,274 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4a194c513/23a955c2402044419cb583f6f0c095ee [2022-07-20 21:46:30,276 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-20 21:46:30,277 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-20 21:46:30,278 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-20 21:46:30,278 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-20 21:46:30,281 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-20 21:46:30,281 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,282 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4de28f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30, skipping insertion in model container [2022-07-20 21:46:30,282 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,292 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-20 21:46:30,307 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-20 21:46:30,460 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c[1442,1455] [2022-07-20 21:46:30,508 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-20 21:46:30,517 INFO L203 MainTranslator]: Completed pre-run [2022-07-20 21:46:30,542 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array19_pattern.c[1442,1455] [2022-07-20 21:46:30,571 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-20 21:46:30,584 INFO L208 MainTranslator]: Completed translation [2022-07-20 21:46:30,589 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30 WrapperNode [2022-07-20 21:46:30,590 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-20 21:46:30,591 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-20 21:46:30,591 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-20 21:46:30,591 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-20 21:46:30,597 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,612 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,638 INFO L137 Inliner]: procedures = 18, calls = 20, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 98 [2022-07-20 21:46:30,639 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-20 21:46:30,640 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-20 21:46:30,640 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-20 21:46:30,640 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-20 21:46:30,647 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,648 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,654 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,654 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,673 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,680 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,685 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,688 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-20 21:46:30,690 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-20 21:46:30,691 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-20 21:46:30,692 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-20 21:46:30,692 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (1/1) ... [2022-07-20 21:46:30,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-20 21:46:30,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-20 21:46:30,725 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-20 21:46:30,727 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-20 21:46:30,752 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-20 21:46:30,752 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2022-07-20 21:46:30,752 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-20 21:46:30,756 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-20 21:46:30,756 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-20 21:46:30,756 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2022-07-20 21:46:30,756 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-20 21:46:30,756 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-20 21:46:30,757 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-20 21:46:30,757 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE4 [2022-07-20 21:46:30,842 INFO L234 CfgBuilder]: Building ICFG [2022-07-20 21:46:30,846 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-20 21:46:31,268 INFO L275 CfgBuilder]: Performing block encoding [2022-07-20 21:46:31,273 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-20 21:46:31,273 INFO L299 CfgBuilder]: Removed 5 assume(true) statements. [2022-07-20 21:46:31,275 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.07 09:46:31 BoogieIcfgContainer [2022-07-20 21:46:31,275 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-20 21:46:31,276 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-20 21:46:31,276 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-20 21:46:31,279 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-20 21:46:31,279 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.07 09:46:30" (1/3) ... [2022-07-20 21:46:31,280 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2079a897 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.07 09:46:31, skipping insertion in model container [2022-07-20 21:46:31,280 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.07 09:46:30" (2/3) ... [2022-07-20 21:46:31,280 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2079a897 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.07 09:46:31, skipping insertion in model container [2022-07-20 21:46:31,280 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.07 09:46:31" (3/3) ... [2022-07-20 21:46:31,281 INFO L111 eAbstractionObserver]: Analyzing ICFG array19_pattern.c [2022-07-20 21:46:31,293 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-20 21:46:31,294 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-20 21:46:31,335 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-20 21:46:31,343 INFO L357 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, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@69601111, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@79fd4cab [2022-07-20 21:46:31,343 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-20 21:46:31,347 INFO L276 IsEmpty]: Start isEmpty. Operand has 33 states, 27 states have (on average 1.5925925925925926) internal successors, (43), 28 states have internal predecessors, (43), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:46:31,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-07-20 21:46:31,355 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:46:31,355 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:46:31,356 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:46:31,360 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:46:31,361 INFO L85 PathProgramCache]: Analyzing trace with hash -2132324569, now seen corresponding path program 1 times [2022-07-20 21:46:31,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:46:31,372 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [272523445] [2022-07-20 21:46:31,372 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:46:31,373 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:46:31,373 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:46:31,379 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:46:31,386 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2022-07-20 21:46:31,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:46:31,455 INFO L263 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 1 conjunts are in the unsatisfiable core [2022-07-20 21:46:31,459 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:46:31,477 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-20 21:46:31,477 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:46:31,478 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:46:31,478 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [272523445] [2022-07-20 21:46:31,479 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [272523445] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:46:31,479 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:46:31,479 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-20 21:46:31,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1001110592] [2022-07-20 21:46:31,481 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:46:31,485 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-20 21:46:31,485 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:46:31,506 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-20 21:46:31,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-20 21:46:31,509 INFO L87 Difference]: Start difference. First operand has 33 states, 27 states have (on average 1.5925925925925926) internal successors, (43), 28 states have internal predecessors, (43), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-20 21:46:31,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:46:31,525 INFO L93 Difference]: Finished difference Result 63 states and 97 transitions. [2022-07-20 21:46:31,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-20 21:46:31,527 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-07-20 21:46:31,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:46:31,532 INFO L225 Difference]: With dead ends: 63 [2022-07-20 21:46:31,532 INFO L226 Difference]: Without dead ends: 29 [2022-07-20 21:46:31,535 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-20 21:46:31,538 INFO L413 NwaCegarLoop]: 41 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, 41 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 [2022-07-20 21:46:31,539 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-20 21:46:31,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-07-20 21:46:31,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-07-20 21:46:31,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 24 states have internal predecessors, (31), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:46:31,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 37 transitions. [2022-07-20 21:46:31,575 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 37 transitions. Word has length 15 [2022-07-20 21:46:31,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:46:31,576 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 37 transitions. [2022-07-20 21:46:31,576 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-20 21:46:31,576 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 37 transitions. [2022-07-20 21:46:31,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-07-20 21:46:31,578 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:46:31,578 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:46:31,590 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Forceful destruction successful, exit code 0 [2022-07-20 21:46:31,787 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:46:31,788 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:46:31,788 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:46:31,788 INFO L85 PathProgramCache]: Analyzing trace with hash 1872922357, now seen corresponding path program 1 times [2022-07-20 21:46:31,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:46:31,789 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1438394619] [2022-07-20 21:46:31,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:46:31,790 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:46:31,790 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:46:31,791 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:46:31,793 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2022-07-20 21:46:31,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:46:31,874 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-20 21:46:31,879 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:46:31,994 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-20 21:46:31,994 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:46:31,994 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:46:31,995 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1438394619] [2022-07-20 21:46:31,995 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1438394619] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:46:31,995 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:46:31,995 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-20 21:46:31,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1685603251] [2022-07-20 21:46:31,996 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:46:31,997 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-20 21:46:31,997 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:46:31,997 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-20 21:46:31,998 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-20 21:46:31,998 INFO L87 Difference]: Start difference. First operand 29 states and 37 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:32,041 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:46:32,041 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-07-20 21:46:32,042 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-20 21:46:32,042 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 30 [2022-07-20 21:46:32,042 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:46:32,043 INFO L225 Difference]: With dead ends: 36 [2022-07-20 21:46:32,043 INFO L226 Difference]: Without dead ends: 32 [2022-07-20 21:46:32,044 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-07-20 21:46:32,045 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 12 mSDsluCounter, 49 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:46:32,045 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 84 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-20 21:46:32,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-07-20 21:46:32,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-07-20 21:46:32,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 27 states have (on average 1.2962962962962963) internal successors, (35), 27 states have internal predecessors, (35), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:46:32,051 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-07-20 21:46:32,051 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 30 [2022-07-20 21:46:32,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:46:32,052 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-07-20 21:46:32,052 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:32,053 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-07-20 21:46:32,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-20 21:46:32,054 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:46:32,054 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:46:32,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Forceful destruction successful, exit code 0 [2022-07-20 21:46:32,264 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:46:32,265 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:46:32,265 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:46:32,265 INFO L85 PathProgramCache]: Analyzing trace with hash 212512359, now seen corresponding path program 1 times [2022-07-20 21:46:32,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:46:32,266 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [455263945] [2022-07-20 21:46:32,266 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:46:32,266 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:46:32,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:46:32,268 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:46:32,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2022-07-20 21:46:32,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:46:32,388 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-20 21:46:32,392 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:46:32,610 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-20 21:46:32,611 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:46:32,611 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:46:32,611 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [455263945] [2022-07-20 21:46:32,611 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [455263945] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:46:32,611 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:46:32,611 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-20 21:46:32,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [449401404] [2022-07-20 21:46:32,612 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:46:32,612 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-20 21:46:32,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:46:32,613 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-20 21:46:32,613 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:46:32,613 INFO L87 Difference]: Start difference. First operand 32 states and 41 transitions. Second operand has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:32,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:46:32,630 INFO L93 Difference]: Finished difference Result 61 states and 76 transitions. [2022-07-20 21:46:32,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-20 21:46:32,630 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2022-07-20 21:46:32,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:46:32,631 INFO L225 Difference]: With dead ends: 61 [2022-07-20 21:46:32,631 INFO L226 Difference]: Without dead ends: 37 [2022-07-20 21:46:32,632 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:46:32,633 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 2 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 75 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 75 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:46:32,633 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 96 Invalid, 75 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 75 Unchecked, 0.0s Time] [2022-07-20 21:46:32,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-20 21:46:32,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-07-20 21:46:32,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 31 states have internal predecessors, (39), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:46:32,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 45 transitions. [2022-07-20 21:46:32,657 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 45 transitions. Word has length 35 [2022-07-20 21:46:32,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:46:32,657 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 45 transitions. [2022-07-20 21:46:32,658 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.7142857142857144) internal successors, (26), 6 states have internal predecessors, (26), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:32,658 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 45 transitions. [2022-07-20 21:46:32,660 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-07-20 21:46:32,660 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:46:32,660 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:46:32,674 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Forceful destruction successful, exit code 0 [2022-07-20 21:46:32,871 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:46:32,872 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:46:32,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:46:32,873 INFO L85 PathProgramCache]: Analyzing trace with hash -654332553, now seen corresponding path program 1 times [2022-07-20 21:46:32,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:46:32,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1024251715] [2022-07-20 21:46:32,873 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:46:32,873 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:46:32,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:46:32,875 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:46:32,877 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2022-07-20 21:46:32,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:46:32,970 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-20 21:46:32,972 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:46:33,150 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-20 21:46:33,150 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:46:33,151 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:46:33,151 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1024251715] [2022-07-20 21:46:33,151 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1024251715] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:46:33,151 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:46:33,151 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-20 21:46:33,152 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [247975236] [2022-07-20 21:46:33,152 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:46:33,152 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-20 21:46:33,152 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:46:33,153 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-20 21:46:33,153 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:46:33,153 INFO L87 Difference]: Start difference. First operand 37 states and 45 transitions. Second operand has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:33,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:46:33,164 INFO L93 Difference]: Finished difference Result 66 states and 83 transitions. [2022-07-20 21:46:33,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-20 21:46:33,164 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 38 [2022-07-20 21:46:33,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:46:33,165 INFO L225 Difference]: With dead ends: 66 [2022-07-20 21:46:33,165 INFO L226 Difference]: Without dead ends: 38 [2022-07-20 21:46:33,165 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:46:33,166 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 2 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 58 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:46:33,166 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 92 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 58 Unchecked, 0.0s Time] [2022-07-20 21:46:33,167 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-07-20 21:46:33,171 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-07-20 21:46:33,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 32 states have (on average 1.25) internal successors, (40), 32 states have internal predecessors, (40), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-20 21:46:33,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 46 transitions. [2022-07-20 21:46:33,176 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 46 transitions. Word has length 38 [2022-07-20 21:46:33,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:46:33,176 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 46 transitions. [2022-07-20 21:46:33,176 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.142857142857143) internal successors, (29), 7 states have internal predecessors, (29), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:46:33,176 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 46 transitions. [2022-07-20 21:46:33,177 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-07-20 21:46:33,178 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:46:33,178 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-20 21:46:33,186 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Forceful destruction successful, exit code 0 [2022-07-20 21:46:33,379 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:46:33,379 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:46:33,380 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:46:33,380 INFO L85 PathProgramCache]: Analyzing trace with hash 579061941, now seen corresponding path program 1 times [2022-07-20 21:46:33,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:46:33,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [736840614] [2022-07-20 21:46:33,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:46:33,381 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:46:33,381 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:46:33,382 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:46:33,384 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Waiting until timeout for monitored process [2022-07-20 21:46:33,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:46:33,533 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 28 conjunts are in the unsatisfiable core [2022-07-20 21:46:33,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:46:34,682 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2022-07-20 21:46:35,591 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-20 21:46:35,596 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-20 21:46:35,597 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 35 treesize of output 15 [2022-07-20 21:46:35,747 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-20 21:46:35,747 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:46:36,824 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 59 treesize of output 55 [2022-07-20 21:46:36,834 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 111 treesize of output 107 [2022-07-20 21:47:29,583 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-07-20 21:47:29,584 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:47:29,584 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [736840614] [2022-07-20 21:47:29,584 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [736840614] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:47:29,584 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:47:29,584 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2022-07-20 21:47:29,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1125009205] [2022-07-20 21:47:29,585 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:47:29,585 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2022-07-20 21:47:29,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:47:29,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2022-07-20 21:47:29,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=208, Invalid=1274, Unknown=0, NotChecked=0, Total=1482 [2022-07-20 21:47:29,588 INFO L87 Difference]: Start difference. First operand 38 states and 46 transitions. Second operand has 39 states, 35 states have (on average 1.8) internal successors, (63), 35 states have internal predecessors, (63), 6 states have call successors, (6), 3 states have call predecessors, (6), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-20 21:47:54,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:47:54,884 INFO L93 Difference]: Finished difference Result 128 states and 169 transitions. [2022-07-20 21:47:54,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2022-07-20 21:47:54,884 INFO L78 Accepts]: Start accepts. Automaton has has 39 states, 35 states have (on average 1.8) internal successors, (63), 35 states have internal predecessors, (63), 6 states have call successors, (6), 3 states have call predecessors, (6), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 40 [2022-07-20 21:47:54,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:47:54,888 INFO L225 Difference]: With dead ends: 128 [2022-07-20 21:47:54,888 INFO L226 Difference]: Without dead ends: 100 [2022-07-20 21:47:54,890 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 781 ImplicationChecksByTransitivity, 31.2s TimeCoverageRelationStatistics Valid=394, Invalid=2258, Unknown=0, NotChecked=0, Total=2652 [2022-07-20 21:47:54,890 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 84 mSDsluCounter, 396 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 735 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 377 IncrementalHoareTripleChecker+Unchecked, 8.5s IncrementalHoareTripleChecker+Time [2022-07-20 21:47:54,891 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [85 Valid, 429 Invalid, 735 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 347 Invalid, 0 Unknown, 377 Unchecked, 8.5s Time] [2022-07-20 21:47:54,892 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-07-20 21:47:54,905 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 79. [2022-07-20 21:47:54,905 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 68 states have (on average 1.3088235294117647) internal successors, (89), 68 states have internal predecessors, (89), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-20 21:47:54,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 103 transitions. [2022-07-20 21:47:54,906 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 103 transitions. Word has length 40 [2022-07-20 21:47:54,906 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:47:54,906 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 103 transitions. [2022-07-20 21:47:54,907 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 35 states have (on average 1.8) internal successors, (63), 35 states have internal predecessors, (63), 6 states have call successors, (6), 3 states have call predecessors, (6), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-20 21:47:54,907 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 103 transitions. [2022-07-20 21:47:54,908 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-20 21:47:54,908 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:47:54,909 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2022-07-20 21:47:54,918 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Forceful destruction successful, exit code 0 [2022-07-20 21:47:55,109 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:47:55,110 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:47:55,110 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:47:55,110 INFO L85 PathProgramCache]: Analyzing trace with hash -1706965193, now seen corresponding path program 2 times [2022-07-20 21:47:55,110 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:47:55,110 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [671599920] [2022-07-20 21:47:55,110 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-20 21:47:55,111 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:47:55,111 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:47:55,144 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:47:55,145 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2022-07-20 21:47:55,324 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-20 21:47:55,325 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:47:55,335 INFO L263 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 19 conjunts are in the unsatisfiable core [2022-07-20 21:47:55,338 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:18,946 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-20 21:48:18,946 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:48:19,562 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-07-20 21:48:19,563 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:19,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [671599920] [2022-07-20 21:48:19,563 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [671599920] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:48:19,563 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:48:19,563 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 7] total 22 [2022-07-20 21:48:19,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1620765006] [2022-07-20 21:48:19,563 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:48:19,564 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-07-20 21:48:19,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:19,564 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-07-20 21:48:19,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=359, Unknown=6, NotChecked=0, Total=462 [2022-07-20 21:48:19,565 INFO L87 Difference]: Start difference. First operand 79 states and 103 transitions. Second operand has 22 states, 20 states have (on average 2.95) internal successors, (59), 20 states have internal predecessors, (59), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:19,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:19,861 INFO L93 Difference]: Finished difference Result 126 states and 168 transitions. [2022-07-20 21:48:19,863 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-07-20 21:48:19,863 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.95) internal successors, (59), 20 states have internal predecessors, (59), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 42 [2022-07-20 21:48:19,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:19,864 INFO L225 Difference]: With dead ends: 126 [2022-07-20 21:48:19,864 INFO L226 Difference]: Without dead ends: 122 [2022-07-20 21:48:19,865 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 61 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 23.5s TimeCoverageRelationStatistics Valid=103, Invalid=397, Unknown=6, NotChecked=0, Total=506 [2022-07-20 21:48:19,866 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 15 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 82 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 63 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:19,866 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 137 Invalid, 82 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 18 Invalid, 0 Unknown, 63 Unchecked, 0.1s Time] [2022-07-20 21:48:19,868 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2022-07-20 21:48:19,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 99. [2022-07-20 21:48:19,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 85 states have (on average 1.3294117647058823) internal successors, (113), 85 states have internal predecessors, (113), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-20 21:48:19,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 131 transitions. [2022-07-20 21:48:19,898 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 131 transitions. Word has length 42 [2022-07-20 21:48:19,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:19,898 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 131 transitions. [2022-07-20 21:48:19,899 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.95) internal successors, (59), 20 states have internal predecessors, (59), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:19,900 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 131 transitions. [2022-07-20 21:48:19,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-20 21:48:19,906 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:19,906 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2022-07-20 21:48:19,920 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:20,118 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:20,118 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:20,118 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:20,119 INFO L85 PathProgramCache]: Analyzing trace with hash 460196979, now seen corresponding path program 3 times [2022-07-20 21:48:20,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:20,119 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1018100024] [2022-07-20 21:48:20,119 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-20 21:48:20,119 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:20,119 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:20,120 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:20,122 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Waiting until timeout for monitored process [2022-07-20 21:48:20,249 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-20 21:48:20,250 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:48:20,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 21 conjunts are in the unsatisfiable core [2022-07-20 21:48:20,262 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:20,991 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 28 [2022-07-20 21:48:23,356 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-20 21:48:23,356 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 45 treesize of output 45 [2022-07-20 21:48:28,926 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-07-20 21:48:28,926 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:48:30,559 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 59 treesize of output 55 [2022-07-20 21:48:30,562 INFO L390 Elim1Store]: Elim1 did not use preprocessing 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 111 treesize of output 107 [2022-07-20 21:48:43,210 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-07-20 21:48:43,210 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:43,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1018100024] [2022-07-20 21:48:43,211 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1018100024] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:48:43,211 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:48:43,211 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 29 [2022-07-20 21:48:43,211 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [450005509] [2022-07-20 21:48:43,211 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:48:43,212 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2022-07-20 21:48:43,212 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:43,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2022-07-20 21:48:43,213 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=691, Unknown=0, NotChecked=0, Total=812 [2022-07-20 21:48:43,213 INFO L87 Difference]: Start difference. First operand 99 states and 131 transitions. Second operand has 29 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 27 states have internal predecessors, (60), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:43,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:43,412 INFO L93 Difference]: Finished difference Result 154 states and 200 transitions. [2022-07-20 21:48:43,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-07-20 21:48:43,413 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 27 states have internal predecessors, (60), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) Word has length 42 [2022-07-20 21:48:43,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:43,414 INFO L225 Difference]: With dead ends: 154 [2022-07-20 21:48:43,414 INFO L226 Difference]: Without dead ends: 150 [2022-07-20 21:48:43,415 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 12.2s TimeCoverageRelationStatistics Valid=121, Invalid=691, Unknown=0, NotChecked=0, Total=812 [2022-07-20 21:48:43,416 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 22 mSDsluCounter, 172 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 189 SdHoareTripleChecker+Invalid, 104 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 80 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:43,416 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 189 Invalid, 104 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 80 Unchecked, 0.2s Time] [2022-07-20 21:48:43,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2022-07-20 21:48:43,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 91. [2022-07-20 21:48:43,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 77 states have (on average 1.3116883116883118) internal successors, (101), 77 states have internal predecessors, (101), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-20 21:48:43,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 119 transitions. [2022-07-20 21:48:43,434 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 119 transitions. Word has length 42 [2022-07-20 21:48:43,434 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:43,435 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 119 transitions. [2022-07-20 21:48:43,435 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 2.0689655172413794) internal successors, (60), 27 states have internal predecessors, (60), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:43,435 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 119 transitions. [2022-07-20 21:48:43,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-20 21:48:43,436 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:43,436 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2022-07-20 21:48:43,451 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:43,647 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:43,647 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:43,648 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:43,648 INFO L85 PathProgramCache]: Analyzing trace with hash -126609035, now seen corresponding path program 1 times [2022-07-20 21:48:43,648 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:43,648 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [160194505] [2022-07-20 21:48:43,648 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:48:43,648 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:43,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:43,650 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:43,650 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Waiting until timeout for monitored process [2022-07-20 21:48:43,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:48:43,728 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 2 conjunts are in the unsatisfiable core [2022-07-20 21:48:43,730 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:43,774 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-07-20 21:48:43,774 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:48:43,774 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:43,775 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [160194505] [2022-07-20 21:48:43,775 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [160194505] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:48:43,775 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:48:43,775 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-20 21:48:43,775 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [445236391] [2022-07-20 21:48:43,775 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:48:43,775 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-07-20 21:48:43,775 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:43,776 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-07-20 21:48:43,776 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-20 21:48:43,776 INFO L87 Difference]: Start difference. First operand 91 states and 119 transitions. Second operand has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-20 21:48:44,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:44,310 INFO L93 Difference]: Finished difference Result 151 states and 196 transitions. [2022-07-20 21:48:44,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-07-20 21:48:44,311 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 42 [2022-07-20 21:48:44,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:44,312 INFO L225 Difference]: With dead ends: 151 [2022-07-20 21:48:44,312 INFO L226 Difference]: Without dead ends: 119 [2022-07-20 21:48:44,312 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-20 21:48:44,313 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 14 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:44,313 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 48 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-07-20 21:48:44,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-07-20 21:48:44,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 95. [2022-07-20 21:48:44,333 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 81 states have (on average 1.2962962962962963) internal successors, (105), 81 states have internal predecessors, (105), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-20 21:48:44,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 123 transitions. [2022-07-20 21:48:44,333 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 123 transitions. Word has length 42 [2022-07-20 21:48:44,334 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:44,334 INFO L495 AbstractCegarLoop]: Abstraction has 95 states and 123 transitions. [2022-07-20 21:48:44,334 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-20 21:48:44,334 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 123 transitions. [2022-07-20 21:48:44,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-20 21:48:44,335 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:44,335 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2022-07-20 21:48:44,345 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:44,544 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:44,545 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:44,545 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:44,545 INFO L85 PathProgramCache]: Analyzing trace with hash -819666699, now seen corresponding path program 1 times [2022-07-20 21:48:44,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:44,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [406901277] [2022-07-20 21:48:44,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:48:44,546 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:44,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:44,547 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:44,549 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Waiting until timeout for monitored process [2022-07-20 21:48:44,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:48:44,621 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 2 conjunts are in the unsatisfiable core [2022-07-20 21:48:44,622 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:44,649 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-07-20 21:48:44,650 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:48:44,650 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:44,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [406901277] [2022-07-20 21:48:44,650 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [406901277] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:48:44,650 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:48:44,650 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-20 21:48:44,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423822322] [2022-07-20 21:48:44,651 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:48:44,651 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-07-20 21:48:44,651 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:44,652 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-07-20 21:48:44,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-20 21:48:44,652 INFO L87 Difference]: Start difference. First operand 95 states and 123 transitions. Second operand has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-20 21:48:44,914 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:44,914 INFO L93 Difference]: Finished difference Result 157 states and 202 transitions. [2022-07-20 21:48:44,916 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-07-20 21:48:44,916 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 42 [2022-07-20 21:48:44,916 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:44,917 INFO L225 Difference]: With dead ends: 157 [2022-07-20 21:48:44,917 INFO L226 Difference]: Without dead ends: 118 [2022-07-20 21:48:44,917 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-07-20 21:48:44,918 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 14 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 58 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:44,918 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 58 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-20 21:48:44,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2022-07-20 21:48:44,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 84. [2022-07-20 21:48:44,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 72 states have (on average 1.25) internal successors, (90), 72 states have internal predecessors, (90), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-20 21:48:44,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 104 transitions. [2022-07-20 21:48:44,940 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 104 transitions. Word has length 42 [2022-07-20 21:48:44,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:44,941 INFO L495 AbstractCegarLoop]: Abstraction has 84 states and 104 transitions. [2022-07-20 21:48:44,941 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 9.333333333333334) internal successors, (28), 3 states have internal predecessors, (28), 1 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-20 21:48:44,941 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 104 transitions. [2022-07-20 21:48:44,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-20 21:48:44,942 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:44,942 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2022-07-20 21:48:44,953 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:45,147 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:45,147 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:45,148 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:45,148 INFO L85 PathProgramCache]: Analyzing trace with hash -1406472713, now seen corresponding path program 1 times [2022-07-20 21:48:45,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:45,148 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [813556672] [2022-07-20 21:48:45,148 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-20 21:48:45,148 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:45,148 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:45,149 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:45,152 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Waiting until timeout for monitored process [2022-07-20 21:48:45,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-20 21:48:45,231 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-20 21:48:45,233 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:45,597 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-20 21:48:45,597 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:48:46,025 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-07-20 21:48:46,025 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:46,025 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [813556672] [2022-07-20 21:48:46,025 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [813556672] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:48:46,025 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:48:46,025 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9] total 20 [2022-07-20 21:48:46,025 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1883766005] [2022-07-20 21:48:46,026 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:48:46,026 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-07-20 21:48:46,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:46,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-07-20 21:48:46,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=282, Unknown=0, NotChecked=0, Total=380 [2022-07-20 21:48:46,027 INFO L87 Difference]: Start difference. First operand 84 states and 104 transitions. Second operand has 20 states, 20 states have (on average 2.3) internal successors, (46), 19 states have internal predecessors, (46), 3 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-07-20 21:48:47,924 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:47,924 INFO L93 Difference]: Finished difference Result 155 states and 196 transitions. [2022-07-20 21:48:47,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2022-07-20 21:48:47,931 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.3) internal successors, (46), 19 states have internal predecessors, (46), 3 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 42 [2022-07-20 21:48:47,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:47,932 INFO L225 Difference]: With dead ends: 155 [2022-07-20 21:48:47,932 INFO L226 Difference]: Without dead ends: 106 [2022-07-20 21:48:47,933 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 288 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=242, Invalid=750, Unknown=0, NotChecked=0, Total=992 [2022-07-20 21:48:47,934 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 20 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 236 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 82 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:47,934 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 126 Invalid, 236 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 132 Invalid, 0 Unknown, 82 Unchecked, 0.8s Time] [2022-07-20 21:48:47,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2022-07-20 21:48:47,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 94. [2022-07-20 21:48:47,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 82 states have (on average 1.2682926829268293) internal successors, (104), 82 states have internal predecessors, (104), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-20 21:48:47,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 118 transitions. [2022-07-20 21:48:47,950 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 118 transitions. Word has length 42 [2022-07-20 21:48:47,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:47,951 INFO L495 AbstractCegarLoop]: Abstraction has 94 states and 118 transitions. [2022-07-20 21:48:47,951 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.3) internal successors, (46), 19 states have internal predecessors, (46), 3 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-07-20 21:48:47,951 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 118 transitions. [2022-07-20 21:48:47,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-20 21:48:47,952 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:47,952 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 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] [2022-07-20 21:48:47,960 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:48,155 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:48,156 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:48,156 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:48,156 INFO L85 PathProgramCache]: Analyzing trace with hash -1439159703, now seen corresponding path program 4 times [2022-07-20 21:48:48,156 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:48,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1298370334] [2022-07-20 21:48:48,157 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-20 21:48:48,157 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:48,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:48,158 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:48,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Waiting until timeout for monitored process [2022-07-20 21:48:48,239 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-20 21:48:48,239 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:48:48,245 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-20 21:48:48,246 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:48,509 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 7 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2022-07-20 21:48:48,509 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:48:48,754 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-07-20 21:48:48,754 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:48,755 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1298370334] [2022-07-20 21:48:48,755 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1298370334] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:48:48,755 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:48:48,755 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 16 [2022-07-20 21:48:48,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1039765801] [2022-07-20 21:48:48,755 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:48:48,756 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-07-20 21:48:48,756 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:48,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-07-20 21:48:48,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2022-07-20 21:48:48,757 INFO L87 Difference]: Start difference. First operand 94 states and 118 transitions. Second operand has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:49,343 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:49,344 INFO L93 Difference]: Finished difference Result 132 states and 167 transitions. [2022-07-20 21:48:49,344 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-07-20 21:48:49,344 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) Word has length 43 [2022-07-20 21:48:49,345 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:49,346 INFO L225 Difference]: With dead ends: 132 [2022-07-20 21:48:49,346 INFO L226 Difference]: Without dead ends: 121 [2022-07-20 21:48:49,346 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 98 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=139, Invalid=281, Unknown=0, NotChecked=0, Total=420 [2022-07-20 21:48:49,347 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 133 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 263 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 146 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:49,347 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 109 Invalid, 263 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 75 Invalid, 0 Unknown, 146 Unchecked, 0.4s Time] [2022-07-20 21:48:49,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-07-20 21:48:49,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 88. [2022-07-20 21:48:49,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 76 states have (on average 1.236842105263158) internal successors, (94), 76 states have internal predecessors, (94), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-20 21:48:49,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 108 transitions. [2022-07-20 21:48:49,362 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 108 transitions. Word has length 43 [2022-07-20 21:48:49,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:49,362 INFO L495 AbstractCegarLoop]: Abstraction has 88 states and 108 transitions. [2022-07-20 21:48:49,362 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.5) internal successors, (56), 16 states have internal predecessors, (56), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 3 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:48:49,363 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 108 transitions. [2022-07-20 21:48:49,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-20 21:48:49,363 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:49,363 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 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] [2022-07-20 21:48:49,371 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:49,567 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:49,567 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:49,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:49,568 INFO L85 PathProgramCache]: Analyzing trace with hash -449271315, now seen corresponding path program 2 times [2022-07-20 21:48:49,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:49,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [446751971] [2022-07-20 21:48:49,568 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-20 21:48:49,569 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:49,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:49,570 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:49,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Waiting until timeout for monitored process [2022-07-20 21:48:49,652 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-20 21:48:49,652 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:48:49,657 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-20 21:48:49,659 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:48:49,832 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-07-20 21:48:49,833 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-20 21:48:49,833 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:48:49,833 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [446751971] [2022-07-20 21:48:49,833 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [446751971] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-20 21:48:49,833 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-20 21:48:49,833 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-20 21:48:49,833 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [146185167] [2022-07-20 21:48:49,833 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-20 21:48:49,834 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-20 21:48:49,834 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:48:49,834 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-20 21:48:49,834 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:48:49,834 INFO L87 Difference]: Start difference. First operand 88 states and 108 transitions. Second operand has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:48:49,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:48:49,852 INFO L93 Difference]: Finished difference Result 140 states and 172 transitions. [2022-07-20 21:48:49,852 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-20 21:48:49,853 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 43 [2022-07-20 21:48:49,853 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:48:49,853 INFO L225 Difference]: With dead ends: 140 [2022-07-20 21:48:49,853 INFO L226 Difference]: Without dead ends: 89 [2022-07-20 21:48:49,854 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2022-07-20 21:48:49,854 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 3 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 41 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-20 21:48:49,855 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 89 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 41 Unchecked, 0.0s Time] [2022-07-20 21:48:49,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2022-07-20 21:48:49,868 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2022-07-20 21:48:49,869 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 77 states have internal predecessors, (94), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-20 21:48:49,869 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 108 transitions. [2022-07-20 21:48:49,869 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 108 transitions. Word has length 43 [2022-07-20 21:48:49,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:48:49,870 INFO L495 AbstractCegarLoop]: Abstraction has 89 states and 108 transitions. [2022-07-20 21:48:49,870 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.857142857142857) internal successors, (34), 7 states have internal predecessors, (34), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-20 21:48:49,870 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 108 transitions. [2022-07-20 21:48:49,871 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-07-20 21:48:49,871 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:48:49,871 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 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, 1, 1] [2022-07-20 21:48:49,885 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Forceful destruction successful, exit code 0 [2022-07-20 21:48:50,085 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:48:50,086 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:48:50,086 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:48:50,086 INFO L85 PathProgramCache]: Analyzing trace with hash 822903975, now seen corresponding path program 5 times [2022-07-20 21:48:50,086 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:48:50,086 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [19936999] [2022-07-20 21:48:50,087 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-20 21:48:50,087 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:48:50,087 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:48:50,088 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:48:50,089 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Waiting until timeout for monitored process [2022-07-20 21:48:50,200 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2022-07-20 21:48:50,200 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:48:50,210 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 18 conjunts are in the unsatisfiable core [2022-07-20 21:48:50,211 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:49:00,801 WARN L233 SmtUtils]: Spent 8.08s on a formula simplification. DAG size of input: 27 DAG size of output: 21 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-20 21:49:15,244 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 19 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-20 21:49:15,245 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:49:15,848 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 7 proven. 4 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-07-20 21:49:15,849 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:49:15,849 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [19936999] [2022-07-20 21:49:15,849 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [19936999] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:49:15,849 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:49:15,849 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 23 [2022-07-20 21:49:15,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [83196876] [2022-07-20 21:49:15,849 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:49:15,850 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-20 21:49:15,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:49:15,850 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-20 21:49:15,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=403, Unknown=5, NotChecked=0, Total=506 [2022-07-20 21:49:15,851 INFO L87 Difference]: Start difference. First operand 89 states and 108 transitions. Second operand has 23 states, 21 states have (on average 3.0476190476190474) internal successors, (64), 20 states have internal predecessors, (64), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:49:16,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:49:16,221 INFO L93 Difference]: Finished difference Result 138 states and 163 transitions. [2022-07-20 21:49:16,222 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-07-20 21:49:16,222 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 21 states have (on average 3.0476190476190474) internal successors, (64), 20 states have internal predecessors, (64), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 45 [2022-07-20 21:49:16,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:49:16,223 INFO L225 Difference]: With dead ends: 138 [2022-07-20 21:49:16,223 INFO L226 Difference]: Without dead ends: 126 [2022-07-20 21:49:16,223 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 142 ImplicationChecksByTransitivity, 25.0s TimeCoverageRelationStatistics Valid=104, Invalid=443, Unknown=5, NotChecked=0, Total=552 [2022-07-20 21:49:16,224 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 11 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 83 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-20 21:49:16,224 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 186 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 17 Invalid, 0 Unknown, 83 Unchecked, 0.1s Time] [2022-07-20 21:49:16,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-07-20 21:49:16,244 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 117. [2022-07-20 21:49:16,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 99 states have (on average 1.1919191919191918) internal successors, (118), 99 states have internal predecessors, (118), 9 states have call successors, (9), 8 states have call predecessors, (9), 8 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-20 21:49:16,245 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 136 transitions. [2022-07-20 21:49:16,246 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 136 transitions. Word has length 45 [2022-07-20 21:49:16,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:49:16,247 INFO L495 AbstractCegarLoop]: Abstraction has 117 states and 136 transitions. [2022-07-20 21:49:16,247 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 21 states have (on average 3.0476190476190474) internal successors, (64), 20 states have internal predecessors, (64), 4 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:49:16,247 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 136 transitions. [2022-07-20 21:49:16,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-20 21:49:16,248 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:49:16,248 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 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] [2022-07-20 21:49:16,263 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Ended with exit code 0 [2022-07-20 21:49:16,460 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:49:16,460 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:49:16,461 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:49:16,461 INFO L85 PathProgramCache]: Analyzing trace with hash 1412646757, now seen corresponding path program 6 times [2022-07-20 21:49:16,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:49:16,461 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1498006864] [2022-07-20 21:49:16,461 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-20 21:49:16,461 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:49:16,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:49:16,462 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:49:16,463 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Waiting until timeout for monitored process [2022-07-20 21:49:16,637 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-07-20 21:49:16,637 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:49:16,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-20 21:49:16,648 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:49:17,183 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 19 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-07-20 21:49:17,184 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:49:17,968 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 4 proven. 14 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-07-20 21:49:17,969 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:49:17,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1498006864] [2022-07-20 21:49:17,969 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1498006864] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:49:17,969 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-20 21:49:17,969 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12] total 19 [2022-07-20 21:49:17,969 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1615648185] [2022-07-20 21:49:17,969 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-20 21:49:17,970 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-20 21:49:17,970 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:49:17,970 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-20 21:49:17,970 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2022-07-20 21:49:17,970 INFO L87 Difference]: Start difference. First operand 117 states and 136 transitions. Second operand has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:49:18,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-20 21:49:18,797 INFO L93 Difference]: Finished difference Result 191 states and 222 transitions. [2022-07-20 21:49:18,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-20 21:49:18,799 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 47 [2022-07-20 21:49:18,799 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-20 21:49:18,800 INFO L225 Difference]: With dead ends: 191 [2022-07-20 21:49:18,800 INFO L226 Difference]: Without dead ends: 157 [2022-07-20 21:49:18,800 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 130 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=114, Invalid=392, Unknown=0, NotChecked=0, Total=506 [2022-07-20 21:49:18,801 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 60 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 91 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-20 21:49:18,801 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 164 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 104 Invalid, 0 Unknown, 91 Unchecked, 0.5s Time] [2022-07-20 21:49:18,802 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2022-07-20 21:49:18,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 151. [2022-07-20 21:49:18,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 129 states have (on average 1.193798449612403) internal successors, (154), 129 states have internal predecessors, (154), 11 states have call successors, (11), 10 states have call predecessors, (11), 10 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-20 21:49:18,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 176 transitions. [2022-07-20 21:49:18,827 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 176 transitions. Word has length 47 [2022-07-20 21:49:18,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-20 21:49:18,828 INFO L495 AbstractCegarLoop]: Abstraction has 151 states and 176 transitions. [2022-07-20 21:49:18,828 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.473684210526316) internal successors, (66), 19 states have internal predecessors, (66), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2022-07-20 21:49:18,828 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 176 transitions. [2022-07-20 21:49:18,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-20 21:49:18,829 INFO L187 NwaCegarLoop]: Found error trace [2022-07-20 21:49:18,829 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 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] [2022-07-20 21:49:18,838 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Forceful destruction successful, exit code 0 [2022-07-20 21:49:19,029 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2022-07-20 21:49:19,030 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-20 21:49:19,030 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-20 21:49:19,030 INFO L85 PathProgramCache]: Analyzing trace with hash -2057551895, now seen corresponding path program 3 times [2022-07-20 21:49:19,031 INFO L118 FreeRefinementEngine]: Executing refinement strategy WOLF [2022-07-20 21:49:19,031 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1225226822] [2022-07-20 21:49:19,031 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-20 21:49:19,031 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2022-07-20 21:49:19,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2022-07-20 21:49:19,032 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2022-07-20 21:49:19,035 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (16)] Waiting until timeout for monitored process [2022-07-20 21:49:19,121 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-20 21:49:19,121 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:49:19,126 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 13 conjunts are in the unsatisfiable core [2022-07-20 21:49:19,127 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:49:26,687 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-07-20 21:49:26,687 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:49:27,348 INFO L136 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2022-07-20 21:49:27,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1225226822] [2022-07-20 21:49:27,349 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1225226822] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-20 21:49:27,349 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1521547565] [2022-07-20 21:49:27,349 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-20 21:49:27,349 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2022-07-20 21:49:27,349 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2022-07-20 21:49:27,351 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2022-07-20 21:49:27,351 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (17)] Waiting until timeout for monitored process [2022-07-20 21:49:27,464 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-20 21:49:27,464 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-20 21:49:27,465 INFO L263 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-20 21:49:27,466 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-20 21:49:44,120 WARN L233 SmtUtils]: Spent 8.09s on a formula simplification. DAG size of input: 27 DAG size of output: 21 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-20 21:49:44,899 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-07-20 21:49:44,900 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-20 21:49:45,593 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-20 21:49:45,593 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1521547565] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-20 21:49:45,593 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-20 21:49:45,594 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 10] total 25 [2022-07-20 21:49:45,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2001320044] [2022-07-20 21:49:45,594 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-20 21:49:45,594 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-07-20 21:49:45,594 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2022-07-20 21:49:45,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-07-20 21:49:45,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=512, Unknown=3, NotChecked=0, Total=650 [2022-07-20 21:49:45,595 INFO L87 Difference]: Start difference. First operand 151 states and 176 transitions. Second operand has 25 states, 20 states have (on average 3.25) internal successors, (65), 20 states have internal predecessors, (65), 7 states have call successors, (8), 3 states have call predecessors, (8), 5 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8)