./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array24_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array24_pattern.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b41c571dabcbc4670dde65107f8da5b879f13435b678b4e9a9cdcc7ef0066cf6 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-10 22:14:34,025 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-10 22:14:34,094 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-10 22:14:34,099 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-10 22:14:34,103 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-10 22:14:34,135 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-10 22:14:34,136 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-10 22:14:34,137 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-10 22:14:34,137 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-10 22:14:34,139 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-10 22:14:34,140 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-10 22:14:34,140 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-10 22:14:34,141 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-10 22:14:34,143 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-10 22:14:34,143 INFO L153 SettingsManager]: * Use SBE=true [2024-10-10 22:14:34,144 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-10 22:14:34,144 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-10 22:14:34,144 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-10 22:14:34,144 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-10 22:14:34,145 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-10 22:14:34,145 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-10 22:14:34,149 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-10 22:14:34,150 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-10 22:14:34,150 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-10 22:14:34,150 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-10 22:14:34,150 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-10 22:14:34,150 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-10 22:14:34,151 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-10 22:14:34,151 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-10 22:14:34,151 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-10 22:14:34,151 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-10 22:14:34,152 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-10 22:14:34,152 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-10 22:14:34,152 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-10 22:14:34,152 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-10 22:14:34,152 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-10 22:14:34,153 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-10 22:14:34,153 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-10 22:14:34,154 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-10 22:14:34,155 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-10 22:14:34,155 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-10 22:14:34,156 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-10 22:14:34,156 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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-clean/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-clean/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b41c571dabcbc4670dde65107f8da5b879f13435b678b4e9a9cdcc7ef0066cf6 [2024-10-10 22:14:34,394 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-10 22:14:34,417 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-10 22:14:34,421 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-10 22:14:34,422 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-10 22:14:34,422 INFO L274 PluginConnector]: CDTParser initialized [2024-10-10 22:14:34,424 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array24_pattern.c [2024-10-10 22:14:35,781 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-10 22:14:35,960 INFO L384 CDTParser]: Found 1 translation units. [2024-10-10 22:14:35,960 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/array-patterns/array24_pattern.c [2024-10-10 22:14:35,967 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/7c1db706a/9ef372de2ea547378330aa93683da341/FLAG4a5ae1cfd [2024-10-10 22:14:36,349 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/7c1db706a/9ef372de2ea547378330aa93683da341 [2024-10-10 22:14:36,352 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-10 22:14:36,353 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-10 22:14:36,354 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-10 22:14:36,354 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-10 22:14:36,359 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-10 22:14:36,360 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,361 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@40c2e52f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36, skipping insertion in model container [2024-10-10 22:14:36,361 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,381 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-10 22:14:36,558 WARN L248 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/array24_pattern.c[1359,1372] [2024-10-10 22:14:36,586 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-10 22:14:36,598 INFO L200 MainTranslator]: Completed pre-run [2024-10-10 22:14:36,640 WARN L248 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/array24_pattern.c[1359,1372] [2024-10-10 22:14:36,652 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-10 22:14:36,667 INFO L204 MainTranslator]: Completed translation [2024-10-10 22:14:36,668 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36 WrapperNode [2024-10-10 22:14:36,677 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-10 22:14:36,679 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-10 22:14:36,679 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-10 22:14:36,679 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-10 22:14:36,685 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,691 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,709 INFO L138 Inliner]: procedures = 17, calls = 20, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 107 [2024-10-10 22:14:36,712 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-10 22:14:36,713 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-10 22:14:36,713 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-10 22:14:36,713 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-10 22:14:36,722 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,723 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,725 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,745 INFO L175 MemorySlicer]: Split 6 memory accesses to 2 slices as follows [2, 4]. 67 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 2 writes are split as follows [0, 2]. [2024-10-10 22:14:36,746 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,749 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,755 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,759 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,760 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,761 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,762 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-10 22:14:36,763 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-10 22:14:36,763 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-10 22:14:36,764 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-10 22:14:36,764 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (1/1) ... [2024-10-10 22:14:36,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-10 22:14:36,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:36,798 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-10 22:14:36,801 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-10 22:14:36,852 INFO L130 BoogieDeclarations]: Found specification of procedure outerBoundaryPatternCheck [2024-10-10 22:14:36,852 INFO L138 BoogieDeclarations]: Found implementation of procedure outerBoundaryPatternCheck [2024-10-10 22:14:36,852 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-10 22:14:36,853 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-10 22:14:36,853 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-10 22:14:36,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-10 22:14:36,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-10-10 22:14:36,855 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-10-10 22:14:36,855 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-10-10 22:14:36,855 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-10-10 22:14:36,855 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-10 22:14:36,855 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-10 22:14:36,856 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-10-10 22:14:36,856 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-10-10 22:14:36,856 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-10-10 22:14:36,935 INFO L238 CfgBuilder]: Building ICFG [2024-10-10 22:14:36,937 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-10 22:14:37,184 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2024-10-10 22:14:37,185 INFO L287 CfgBuilder]: Performing block encoding [2024-10-10 22:14:37,224 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-10 22:14:37,227 INFO L314 CfgBuilder]: Removed 5 assume(true) statements. [2024-10-10 22:14:37,227 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 10:14:37 BoogieIcfgContainer [2024-10-10 22:14:37,228 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-10 22:14:37,230 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-10 22:14:37,231 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-10 22:14:37,235 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-10 22:14:37,235 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.10 10:14:36" (1/3) ... [2024-10-10 22:14:37,236 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ffc6a90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.10 10:14:37, skipping insertion in model container [2024-10-10 22:14:37,236 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.10 10:14:36" (2/3) ... [2024-10-10 22:14:37,237 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ffc6a90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.10 10:14:37, skipping insertion in model container [2024-10-10 22:14:37,238 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 10:14:37" (3/3) ... [2024-10-10 22:14:37,239 INFO L112 eAbstractionObserver]: Analyzing ICFG array24_pattern.c [2024-10-10 22:14:37,255 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-10 22:14:37,256 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-10 22:14:37,317 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-10 22:14:37,323 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@598e49cb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-10 22:14:37,324 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-10 22:14:37,328 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 26 states have (on average 1.6538461538461537) internal successors, (43), 27 states have internal predecessors, (43), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:37,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-10-10 22:14:37,334 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:37,334 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:37,335 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:37,338 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:37,338 INFO L85 PathProgramCache]: Analyzing trace with hash 1644752152, now seen corresponding path program 1 times [2024-10-10 22:14:37,345 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:37,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1533210874] [2024-10-10 22:14:37,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:37,346 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:37,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:37,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:37,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:37,490 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-10 22:14:37,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:37,491 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1533210874] [2024-10-10 22:14:37,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1533210874] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-10 22:14:37,492 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-10 22:14:37,493 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-10-10 22:14:37,494 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1691400696] [2024-10-10 22:14:37,495 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-10 22:14:37,499 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-10-10 22:14:37,499 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:37,527 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-10-10 22:14:37,528 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-10-10 22:14:37,530 INFO L87 Difference]: Start difference. First operand has 35 states, 26 states have (on average 1.6538461538461537) internal successors, (43), 27 states have internal predecessors, (43), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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) [2024-10-10 22:14:37,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:37,567 INFO L93 Difference]: Finished difference Result 68 states and 106 transitions. [2024-10-10 22:14:37,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-10-10 22:14:37,572 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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 14 [2024-10-10 22:14:37,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:37,578 INFO L225 Difference]: With dead ends: 68 [2024-10-10 22:14:37,578 INFO L226 Difference]: Without dead ends: 33 [2024-10-10 22:14:37,581 INFO L431 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 [2024-10-10 22:14:37,586 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:37,588 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 41 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-10 22:14:37,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-10-10 22:14:37,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2024-10-10 22:14:37,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 25 states have (on average 1.32) internal successors, (33), 25 states have internal predecessors, (33), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:37,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2024-10-10 22:14:37,624 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 14 [2024-10-10 22:14:37,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:37,625 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2024-10-10 22:14:37,625 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 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) [2024-10-10 22:14:37,625 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2024-10-10 22:14:37,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-10 22:14:37,627 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:37,627 INFO L215 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] [2024-10-10 22:14:37,628 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-10 22:14:37,628 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:37,629 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:37,629 INFO L85 PathProgramCache]: Analyzing trace with hash -1106245937, now seen corresponding path program 1 times [2024-10-10 22:14:37,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:37,629 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1238480996] [2024-10-10 22:14:37,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:37,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:37,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,012 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:38,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,051 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-10 22:14:38,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,056 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-10 22:14:38,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,064 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-10 22:14:38,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,070 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-10 22:14:38,072 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:38,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1238480996] [2024-10-10 22:14:38,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1238480996] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:38,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [144327371] [2024-10-10 22:14:38,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:38,074 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:38,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:38,076 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:38,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-10 22:14:38,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,166 INFO L255 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-10 22:14:38,174 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:38,298 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-10 22:14:38,299 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-10 22:14:38,299 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [144327371] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-10 22:14:38,299 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-10 22:14:38,299 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-10-10 22:14:38,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [232240005] [2024-10-10 22:14:38,302 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-10 22:14:38,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-10 22:14:38,303 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:38,304 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-10 22:14:38,304 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-10-10 22:14:38,304 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-10 22:14:38,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:38,404 INFO L93 Difference]: Finished difference Result 76 states and 96 transitions. [2024-10-10 22:14:38,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-10 22:14:38,404 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 34 [2024-10-10 22:14:38,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:38,405 INFO L225 Difference]: With dead ends: 76 [2024-10-10 22:14:38,406 INFO L226 Difference]: Without dead ends: 43 [2024-10-10 22:14:38,406 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-10-10 22:14:38,407 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 9 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:38,408 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 115 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:38,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-10-10 22:14:38,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 34. [2024-10-10 22:14:38,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 26 states have (on average 1.3076923076923077) internal successors, (34), 26 states have internal predecessors, (34), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:38,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2024-10-10 22:14:38,415 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 34 [2024-10-10 22:14:38,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:38,416 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2024-10-10 22:14:38,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 3 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-10 22:14:38,416 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2024-10-10 22:14:38,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-10 22:14:38,417 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:38,417 INFO L215 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] [2024-10-10 22:14:38,433 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:38,621 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:38,622 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:38,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:38,622 INFO L85 PathProgramCache]: Analyzing trace with hash 1743944017, now seen corresponding path program 1 times [2024-10-10 22:14:38,623 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:38,623 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1868164435] [2024-10-10 22:14:38,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:38,623 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:38,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,738 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:38,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,744 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-10 22:14:38,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,750 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-10 22:14:38,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,755 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-10 22:14:38,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,761 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-10 22:14:38,761 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:38,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1868164435] [2024-10-10 22:14:38,762 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1868164435] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-10 22:14:38,762 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-10 22:14:38,762 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-10-10 22:14:38,762 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313859804] [2024-10-10 22:14:38,762 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-10 22:14:38,763 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-10-10 22:14:38,763 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:38,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-10-10 22:14:38,766 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-10 22:14:38,766 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-10 22:14:38,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:38,805 INFO L93 Difference]: Finished difference Result 71 states and 95 transitions. [2024-10-10 22:14:38,806 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-10-10 22:14:38,806 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 37 [2024-10-10 22:14:38,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:38,807 INFO L225 Difference]: With dead ends: 71 [2024-10-10 22:14:38,807 INFO L226 Difference]: Without dead ends: 41 [2024-10-10 22:14:38,808 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-10-10 22:14:38,810 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 67 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:38,810 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 67 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-10 22:14:38,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-10-10 22:14:38,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 37. [2024-10-10 22:14:38,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 29 states have internal predecessors, (38), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:38,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2024-10-10 22:14:38,818 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 37 [2024-10-10 22:14:38,818 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:38,818 INFO L471 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2024-10-10 22:14:38,819 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-10-10 22:14:38,819 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2024-10-10 22:14:38,822 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-10 22:14:38,822 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:38,823 INFO L215 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] [2024-10-10 22:14:38,823 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-10-10 22:14:38,823 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:38,824 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:38,824 INFO L85 PathProgramCache]: Analyzing trace with hash -190626440, now seen corresponding path program 1 times [2024-10-10 22:14:38,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:38,824 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675113232] [2024-10-10 22:14:38,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:38,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:38,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,962 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:38,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,966 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-10 22:14:38,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,973 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-10 22:14:38,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,980 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-10 22:14:38,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:38,992 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-10-10 22:14:38,993 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:38,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [675113232] [2024-10-10 22:14:38,993 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [675113232] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:38,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [16037253] [2024-10-10 22:14:38,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:38,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:38,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:38,997 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:38,999 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-10 22:14:39,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,065 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-10 22:14:39,067 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:39,137 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-10 22:14:39,141 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:39,215 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-10-10 22:14:39,215 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [16037253] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:39,215 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:39,215 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 8 [2024-10-10 22:14:39,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [769676274] [2024-10-10 22:14:39,216 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:39,216 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-10-10 22:14:39,216 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:39,217 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-10-10 22:14:39,217 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2024-10-10 22:14:39,217 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:39,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:39,328 INFO L93 Difference]: Finished difference Result 49 states and 60 transitions. [2024-10-10 22:14:39,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-10-10 22:14:39,329 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 38 [2024-10-10 22:14:39,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:39,330 INFO L225 Difference]: With dead ends: 49 [2024-10-10 22:14:39,330 INFO L226 Difference]: Without dead ends: 45 [2024-10-10 22:14:39,330 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2024-10-10 22:14:39,331 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 29 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 109 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:39,332 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 109 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:39,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-10 22:14:39,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 41. [2024-10-10 22:14:39,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 32 states have (on average 1.25) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:39,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2024-10-10 22:14:39,345 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 38 [2024-10-10 22:14:39,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:39,346 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2024-10-10 22:14:39,346 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.875) internal successors, (39), 8 states have internal predecessors, (39), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:39,346 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2024-10-10 22:14:39,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-10-10 22:14:39,348 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:39,348 INFO L215 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, 1, 1] [2024-10-10 22:14:39,367 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-10 22:14:39,549 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:39,549 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:39,550 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:39,550 INFO L85 PathProgramCache]: Analyzing trace with hash -465343306, now seen corresponding path program 1 times [2024-10-10 22:14:39,550 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:39,550 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [549787757] [2024-10-10 22:14:39,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:39,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:39,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,678 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:39,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,698 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-10 22:14:39,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,701 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-10 22:14:39,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,705 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-10 22:14:39,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,711 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-10 22:14:39,712 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:39,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [549787757] [2024-10-10 22:14:39,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [549787757] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:39,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2023777179] [2024-10-10 22:14:39,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:39,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:39,713 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:39,714 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:39,725 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-10 22:14:39,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:39,792 INFO L255 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-10 22:14:39,794 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:39,861 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-10 22:14:39,864 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:40,014 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-10-10 22:14:40,015 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2023777179] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:40,015 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:40,015 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 15 [2024-10-10 22:14:40,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [151627497] [2024-10-10 22:14:40,016 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:40,016 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-10 22:14:40,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:40,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-10 22:14:40,018 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=144, Unknown=0, NotChecked=0, Total=210 [2024-10-10 22:14:40,018 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand has 15 states, 15 states have (on average 3.1333333333333333) internal successors, (47), 14 states have internal predecessors, (47), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-10 22:14:40,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:40,241 INFO L93 Difference]: Finished difference Result 77 states and 99 transitions. [2024-10-10 22:14:40,241 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-10 22:14:40,241 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 3.1333333333333333) internal successors, (47), 14 states have internal predecessors, (47), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) Word has length 42 [2024-10-10 22:14:40,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:40,242 INFO L225 Difference]: With dead ends: 77 [2024-10-10 22:14:40,242 INFO L226 Difference]: Without dead ends: 45 [2024-10-10 22:14:40,243 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 82 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2024-10-10 22:14:40,244 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 58 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 227 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:40,244 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 158 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 227 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-10 22:14:40,244 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-10-10 22:14:40,257 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 43. [2024-10-10 22:14:40,257 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 34 states have (on average 1.2352941176470589) internal successors, (42), 34 states have internal predecessors, (42), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:40,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 52 transitions. [2024-10-10 22:14:40,258 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 52 transitions. Word has length 42 [2024-10-10 22:14:40,258 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:40,258 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 52 transitions. [2024-10-10 22:14:40,259 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 3.1333333333333333) internal successors, (47), 14 states have internal predecessors, (47), 2 states have call successors, (7), 2 states have call predecessors, (7), 4 states have return successors, (8), 3 states have call predecessors, (8), 2 states have call successors, (8) [2024-10-10 22:14:40,259 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 52 transitions. [2024-10-10 22:14:40,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-10-10 22:14:40,260 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:40,260 INFO L215 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, 1, 1] [2024-10-10 22:14:40,272 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:40,461 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:40,462 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:40,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:40,462 INFO L85 PathProgramCache]: Analyzing trace with hash 1367452082, now seen corresponding path program 2 times [2024-10-10 22:14:40,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:40,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1398812092] [2024-10-10 22:14:40,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:40,463 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:40,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:40,574 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:40,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:40,578 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-10 22:14:40,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:40,581 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-10 22:14:40,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:40,585 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-10 22:14:40,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:40,589 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-10 22:14:40,590 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:40,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1398812092] [2024-10-10 22:14:40,590 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1398812092] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:40,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [883477257] [2024-10-10 22:14:40,590 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-10 22:14:40,590 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:40,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:40,593 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:40,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-10 22:14:40,664 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-10 22:14:40,665 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:40,666 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-10 22:14:40,668 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:40,739 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-10 22:14:40,739 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:40,805 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-10 22:14:40,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [883477257] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:40,806 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:40,806 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 15 [2024-10-10 22:14:40,806 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1992166103] [2024-10-10 22:14:40,806 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:40,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-10 22:14:40,807 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:40,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-10 22:14:40,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=153, Unknown=0, NotChecked=0, Total=210 [2024-10-10 22:14:40,809 INFO L87 Difference]: Start difference. First operand 43 states and 52 transitions. Second operand has 15 states, 15 states have (on average 3.6) internal successors, (54), 15 states have internal predecessors, (54), 2 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:40,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:40,947 INFO L93 Difference]: Finished difference Result 91 states and 113 transitions. [2024-10-10 22:14:40,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-10 22:14:40,949 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 3.6) internal successors, (54), 15 states have internal predecessors, (54), 2 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2024-10-10 22:14:40,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:40,949 INFO L225 Difference]: With dead ends: 91 [2024-10-10 22:14:40,949 INFO L226 Difference]: Without dead ends: 61 [2024-10-10 22:14:40,950 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 89 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=90, Invalid=216, Unknown=0, NotChecked=0, Total=306 [2024-10-10 22:14:40,951 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 15 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:40,951 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 160 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:40,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-10-10 22:14:40,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 53. [2024-10-10 22:14:40,966 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 44 states have (on average 1.2272727272727273) internal successors, (54), 44 states have internal predecessors, (54), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-10-10 22:14:40,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 64 transitions. [2024-10-10 22:14:40,971 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 64 transitions. Word has length 44 [2024-10-10 22:14:40,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:40,971 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 64 transitions. [2024-10-10 22:14:40,971 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 3.6) internal successors, (54), 15 states have internal predecessors, (54), 2 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:40,971 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 64 transitions. [2024-10-10 22:14:40,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-10-10 22:14:40,972 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:40,972 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:40,989 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-10 22:14:41,173 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-10-10 22:14:41,173 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:41,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:41,174 INFO L85 PathProgramCache]: Analyzing trace with hash 160309039, now seen corresponding path program 3 times [2024-10-10 22:14:41,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:41,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1820674626] [2024-10-10 22:14:41,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:41,174 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:41,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-10 22:14:41,212 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [595842116] [2024-10-10 22:14:41,212 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-10 22:14:41,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:41,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:41,215 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:41,216 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-10 22:14:41,480 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-10-10 22:14:41,480 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:41,483 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 78 conjuncts are in the unsatisfiable core [2024-10-10 22:14:41,492 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:41,570 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-10-10 22:14:41,608 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2024-10-10 22:14:41,754 INFO L349 Elim1Store]: treesize reduction 32, result has 31.9 percent of original size [2024-10-10 22:14:41,754 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 28 treesize of output 30 [2024-10-10 22:14:41,839 INFO L349 Elim1Store]: treesize reduction 52, result has 22.4 percent of original size [2024-10-10 22:14:41,839 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 39 treesize of output 44 [2024-10-10 22:14:42,650 INFO L349 Elim1Store]: treesize reduction 190, result has 15.6 percent of original size [2024-10-10 22:14:42,651 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 66 treesize of output 62 [2024-10-10 22:14:43,139 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-10-10 22:14:43,140 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-10-10 22:14:43,141 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-10-10 22:14:43,142 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-10-10 22:14:43,145 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:14:43,145 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 35 treesize of output 13 [2024-10-10 22:14:43,258 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 38 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-10 22:14:43,258 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:44,763 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 178 treesize of output 170 [2024-10-10 22:14:44,787 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:14:44,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 79913 treesize of output 72745 [2024-10-10 22:14:45,409 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 38 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-10-10 22:14:45,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:45,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1820674626] [2024-10-10 22:14:45,410 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-10 22:14:45,410 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [595842116] [2024-10-10 22:14:45,410 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [595842116] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:45,411 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-10 22:14:45,411 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 24] total 48 [2024-10-10 22:14:45,411 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1929253519] [2024-10-10 22:14:45,411 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:45,413 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2024-10-10 22:14:45,413 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:45,414 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2024-10-10 22:14:45,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=350, Invalid=1906, Unknown=0, NotChecked=0, Total=2256 [2024-10-10 22:14:45,415 INFO L87 Difference]: Start difference. First operand 53 states and 64 transitions. Second operand has 48 states, 48 states have (on average 1.625) internal successors, (78), 46 states have internal predecessors, (78), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-10 22:14:53,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:53,204 INFO L93 Difference]: Finished difference Result 280 states and 379 transitions. [2024-10-10 22:14:53,204 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2024-10-10 22:14:53,205 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 1.625) internal successors, (78), 46 states have internal predecessors, (78), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) Word has length 54 [2024-10-10 22:14:53,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:53,208 INFO L225 Difference]: With dead ends: 280 [2024-10-10 22:14:53,208 INFO L226 Difference]: Without dead ends: 238 [2024-10-10 22:14:53,213 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 54 SyntacticMatches, 6 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4339 ImplicationChecksByTransitivity, 6.8s TimeCoverageRelationStatistics Valid=1972, Invalid=11600, Unknown=0, NotChecked=0, Total=13572 [2024-10-10 22:14:53,214 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 468 mSDsluCounter, 611 mSDsCounter, 0 mSdLazyCounter, 1974 mSolverCounterSat, 334 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 479 SdHoareTripleChecker+Valid, 646 SdHoareTripleChecker+Invalid, 2308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 334 IncrementalHoareTripleChecker+Valid, 1974 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:53,214 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [479 Valid, 646 Invalid, 2308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [334 Valid, 1974 Invalid, 0 Unknown, 0 Unchecked, 2.8s Time] [2024-10-10 22:14:53,215 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2024-10-10 22:14:53,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 146. [2024-10-10 22:14:53,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 122 states have (on average 1.2868852459016393) internal successors, (157), 121 states have internal predecessors, (157), 17 states have call successors, (17), 5 states have call predecessors, (17), 6 states have return successors, (21), 19 states have call predecessors, (21), 17 states have call successors, (21) [2024-10-10 22:14:53,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 195 transitions. [2024-10-10 22:14:53,276 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 195 transitions. Word has length 54 [2024-10-10 22:14:53,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:53,276 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 195 transitions. [2024-10-10 22:14:53,277 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 48 states have (on average 1.625) internal successors, (78), 46 states have internal predecessors, (78), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (7), 5 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-10 22:14:53,277 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 195 transitions. [2024-10-10 22:14:53,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-10-10 22:14:53,281 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:53,282 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:53,291 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-10 22:14:53,485 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:53,486 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:53,486 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:53,486 INFO L85 PathProgramCache]: Analyzing trace with hash 110261106, now seen corresponding path program 4 times [2024-10-10 22:14:53,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:53,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [90436677] [2024-10-10 22:14:53,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:53,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:53,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:53,623 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:53,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:53,625 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-10 22:14:53,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:53,628 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-10 22:14:53,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:53,632 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-10 22:14:53,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:53,634 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 15 proven. 20 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-10-10 22:14:53,635 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:53,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [90436677] [2024-10-10 22:14:53,635 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [90436677] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:53,635 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1318588996] [2024-10-10 22:14:53,635 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-10 22:14:53,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:53,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:53,637 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:53,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-10 22:14:53,703 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-10 22:14:53,703 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:53,704 INFO L255 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-10 22:14:53,707 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:53,802 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 31 proven. 12 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-10-10 22:14:53,802 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:53,889 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 14 proven. 21 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-10-10 22:14:53,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1318588996] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:53,889 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:53,889 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-10-10 22:14:53,890 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [501461323] [2024-10-10 22:14:53,890 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:53,890 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-10 22:14:53,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:53,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-10 22:14:53,891 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2024-10-10 22:14:53,891 INFO L87 Difference]: Start difference. First operand 146 states and 195 transitions. Second operand has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:54,034 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:54,035 INFO L93 Difference]: Finished difference Result 397 states and 536 transitions. [2024-10-10 22:14:54,035 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-10 22:14:54,035 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2024-10-10 22:14:54,036 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:54,038 INFO L225 Difference]: With dead ends: 397 [2024-10-10 22:14:54,038 INFO L226 Difference]: Without dead ends: 256 [2024-10-10 22:14:54,039 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 108 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2024-10-10 22:14:54,041 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 11 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:54,042 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 214 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:54,042 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2024-10-10 22:14:54,111 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 232. [2024-10-10 22:14:54,112 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 232 states, 191 states have (on average 1.2617801047120418) internal successors, (241), 189 states have internal predecessors, (241), 29 states have call successors, (29), 9 states have call predecessors, (29), 11 states have return successors, (37), 33 states have call predecessors, (37), 29 states have call successors, (37) [2024-10-10 22:14:54,114 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 232 states to 232 states and 307 transitions. [2024-10-10 22:14:54,114 INFO L78 Accepts]: Start accepts. Automaton has 232 states and 307 transitions. Word has length 55 [2024-10-10 22:14:54,114 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:54,114 INFO L471 AbstractCegarLoop]: Abstraction has 232 states and 307 transitions. [2024-10-10 22:14:54,115 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:54,115 INFO L276 IsEmpty]: Start isEmpty. Operand 232 states and 307 transitions. [2024-10-10 22:14:54,117 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-10-10 22:14:54,117 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:54,117 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:54,134 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:54,318 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-10-10 22:14:54,318 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:54,318 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:54,319 INFO L85 PathProgramCache]: Analyzing trace with hash 669382493, now seen corresponding path program 5 times [2024-10-10 22:14:54,319 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:54,319 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2018856200] [2024-10-10 22:14:54,319 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:54,319 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:54,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:54,495 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:54,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:54,498 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-10 22:14:54,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:54,499 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-10-10 22:14:54,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:54,502 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-10-10 22:14:54,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:54,504 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 1 proven. 25 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-10-10 22:14:54,505 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:54,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2018856200] [2024-10-10 22:14:54,505 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2018856200] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:54,505 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [319685757] [2024-10-10 22:14:54,505 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-10-10 22:14:54,505 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:54,505 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:54,507 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:54,509 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-10 22:14:54,585 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2024-10-10 22:14:54,585 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:54,587 INFO L255 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-10 22:14:54,588 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:54,674 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 11 proven. 23 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2024-10-10 22:14:54,675 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:54,754 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 3 proven. 23 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-10-10 22:14:54,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [319685757] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:54,754 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:54,754 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 20 [2024-10-10 22:14:54,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [58080896] [2024-10-10 22:14:54,755 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:54,755 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-10-10 22:14:54,755 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:54,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-10-10 22:14:54,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=287, Unknown=0, NotChecked=0, Total=380 [2024-10-10 22:14:54,756 INFO L87 Difference]: Start difference. First operand 232 states and 307 transitions. Second operand has 20 states, 20 states have (on average 2.9) internal successors, (58), 20 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:54,943 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:54,944 INFO L93 Difference]: Finished difference Result 360 states and 459 transitions. [2024-10-10 22:14:54,944 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-10-10 22:14:54,945 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.9) internal successors, (58), 20 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 58 [2024-10-10 22:14:54,945 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:54,947 INFO L225 Difference]: With dead ends: 360 [2024-10-10 22:14:54,947 INFO L226 Difference]: Without dead ends: 222 [2024-10-10 22:14:54,948 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 110 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 221 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=156, Invalid=444, Unknown=0, NotChecked=0, Total=600 [2024-10-10 22:14:54,948 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 31 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:54,949 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 168 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:54,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2024-10-10 22:14:55,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 187. [2024-10-10 22:14:55,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 154 states have (on average 1.2337662337662338) internal successors, (190), 153 states have internal predecessors, (190), 21 states have call successors, (21), 9 states have call predecessors, (21), 11 states have return successors, (27), 24 states have call predecessors, (27), 21 states have call successors, (27) [2024-10-10 22:14:55,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 238 transitions. [2024-10-10 22:14:55,011 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 238 transitions. Word has length 58 [2024-10-10 22:14:55,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:55,011 INFO L471 AbstractCegarLoop]: Abstraction has 187 states and 238 transitions. [2024-10-10 22:14:55,011 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.9) internal successors, (58), 20 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:55,011 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 238 transitions. [2024-10-10 22:14:55,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-10-10 22:14:55,012 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:55,013 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:55,026 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:55,213 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:55,214 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:55,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:55,214 INFO L85 PathProgramCache]: Analyzing trace with hash -2032202519, now seen corresponding path program 1 times [2024-10-10 22:14:55,214 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:55,214 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573700788] [2024-10-10 22:14:55,214 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:55,214 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:55,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,296 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:55,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,298 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-10 22:14:55,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,302 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-10 22:14:55,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,304 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-10 22:14:55,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,306 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-10 22:14:55,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,325 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-10-10 22:14:55,325 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:55,325 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573700788] [2024-10-10 22:14:55,326 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [573700788] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-10 22:14:55,326 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-10 22:14:55,326 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-10 22:14:55,326 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1957627705] [2024-10-10 22:14:55,326 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-10 22:14:55,327 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-10 22:14:55,327 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:55,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-10 22:14:55,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-10 22:14:55,327 INFO L87 Difference]: Start difference. First operand 187 states and 238 transitions. Second operand has 5 states, 5 states have (on average 6.2) internal successors, (31), 4 states have internal predecessors, (31), 1 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2024-10-10 22:14:55,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:55,386 INFO L93 Difference]: Finished difference Result 275 states and 352 transitions. [2024-10-10 22:14:55,387 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-10 22:14:55,387 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 4 states have internal predecessors, (31), 1 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) Word has length 60 [2024-10-10 22:14:55,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:55,389 INFO L225 Difference]: With dead ends: 275 [2024-10-10 22:14:55,389 INFO L226 Difference]: Without dead ends: 201 [2024-10-10 22:14:55,390 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-10 22:14:55,392 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 144 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.0s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:55,392 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 144 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-10 22:14:55,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-10-10 22:14:55,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 198. [2024-10-10 22:14:55,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 163 states have (on average 1.2208588957055215) internal successors, (199), 159 states have internal predecessors, (199), 21 states have call successors, (21), 9 states have call predecessors, (21), 13 states have return successors, (31), 29 states have call predecessors, (31), 21 states have call successors, (31) [2024-10-10 22:14:55,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 251 transitions. [2024-10-10 22:14:55,441 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 251 transitions. Word has length 60 [2024-10-10 22:14:55,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:55,441 INFO L471 AbstractCegarLoop]: Abstraction has 198 states and 251 transitions. [2024-10-10 22:14:55,442 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.2) internal successors, (31), 4 states have internal predecessors, (31), 1 states have call successors, (5), 1 states have call predecessors, (5), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2024-10-10 22:14:55,442 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 251 transitions. [2024-10-10 22:14:55,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-10-10 22:14:55,444 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:55,444 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:55,444 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-10-10 22:14:55,444 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:55,445 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:55,445 INFO L85 PathProgramCache]: Analyzing trace with hash 224708488, now seen corresponding path program 1 times [2024-10-10 22:14:55,445 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:55,445 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [972713436] [2024-10-10 22:14:55,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:55,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:55,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,630 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:55,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,632 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2024-10-10 22:14:55,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,656 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-10 22:14:55,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,660 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-10 22:14:55,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,712 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-10 22:14:55,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,715 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 5 proven. 18 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-10-10 22:14:55,715 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:55,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [972713436] [2024-10-10 22:14:55,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [972713436] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:55,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1135783893] [2024-10-10 22:14:55,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:55,716 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:55,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:55,718 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:55,719 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-10 22:14:55,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:55,797 INFO L255 TraceCheckSpWp]: Trace formula consists of 201 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-10-10 22:14:55,799 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:55,994 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 16 proven. 12 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-10-10 22:14:55,995 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:56,182 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 11 proven. 12 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-10-10 22:14:56,182 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1135783893] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:56,182 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:56,182 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11] total 22 [2024-10-10 22:14:56,183 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [113841159] [2024-10-10 22:14:56,183 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:56,183 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-10 22:14:56,183 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:56,184 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-10 22:14:56,184 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2024-10-10 22:14:56,184 INFO L87 Difference]: Start difference. First operand 198 states and 251 transitions. Second operand has 22 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 21 states have internal predecessors, (62), 6 states have call successors, (12), 3 states have call predecessors, (12), 8 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2024-10-10 22:14:56,470 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:56,470 INFO L93 Difference]: Finished difference Result 272 states and 332 transitions. [2024-10-10 22:14:56,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-10-10 22:14:56,471 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 21 states have internal predecessors, (62), 6 states have call successors, (12), 3 states have call predecessors, (12), 8 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 60 [2024-10-10 22:14:56,471 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:56,472 INFO L225 Difference]: With dead ends: 272 [2024-10-10 22:14:56,472 INFO L226 Difference]: Without dead ends: 176 [2024-10-10 22:14:56,473 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 113 SyntacticMatches, 4 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2024-10-10 22:14:56,474 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 39 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 331 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 348 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 331 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:56,474 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 242 Invalid, 348 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 331 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-10 22:14:56,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2024-10-10 22:14:56,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 157. [2024-10-10 22:14:56,516 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 133 states have (on average 1.2030075187969924) internal successors, (160), 133 states have internal predecessors, (160), 13 states have call successors, (13), 8 states have call predecessors, (13), 10 states have return successors, (17), 15 states have call predecessors, (17), 13 states have call successors, (17) [2024-10-10 22:14:56,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 190 transitions. [2024-10-10 22:14:56,517 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 190 transitions. Word has length 60 [2024-10-10 22:14:56,517 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:56,517 INFO L471 AbstractCegarLoop]: Abstraction has 157 states and 190 transitions. [2024-10-10 22:14:56,517 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.9523809523809526) internal successors, (62), 21 states have internal predecessors, (62), 6 states have call successors, (12), 3 states have call predecessors, (12), 8 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2024-10-10 22:14:56,518 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 190 transitions. [2024-10-10 22:14:56,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-10-10 22:14:56,519 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:56,519 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 3, 3, 3, 3, 3, 3, 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] [2024-10-10 22:14:56,535 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:56,719 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-10-10 22:14:56,720 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:56,720 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:56,720 INFO L85 PathProgramCache]: Analyzing trace with hash -125029806, now seen corresponding path program 6 times [2024-10-10 22:14:56,720 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:56,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2135102515] [2024-10-10 22:14:56,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:56,720 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:56,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:56,886 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:56,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:56,889 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-10 22:14:56,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:56,891 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-10 22:14:56,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:56,893 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-10 22:14:56,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:56,896 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 24 proven. 15 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-10-10 22:14:56,896 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:56,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2135102515] [2024-10-10 22:14:56,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2135102515] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:56,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1448024760] [2024-10-10 22:14:56,896 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-10-10 22:14:56,896 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:56,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:56,898 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:56,899 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-10 22:14:56,981 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2024-10-10 22:14:56,981 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:56,982 INFO L255 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-10 22:14:56,984 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:57,089 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 44 proven. 3 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2024-10-10 22:14:57,089 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:57,164 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 24 proven. 15 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-10-10 22:14:57,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1448024760] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:57,165 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:57,165 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 19 [2024-10-10 22:14:57,165 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1320555997] [2024-10-10 22:14:57,165 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:57,166 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-10-10 22:14:57,166 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:57,166 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-10-10 22:14:57,166 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=264, Unknown=0, NotChecked=0, Total=342 [2024-10-10 22:14:57,167 INFO L87 Difference]: Start difference. First operand 157 states and 190 transitions. Second operand has 19 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 19 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:57,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:57,366 INFO L93 Difference]: Finished difference Result 197 states and 232 transitions. [2024-10-10 22:14:57,367 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-10 22:14:57,367 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 19 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 64 [2024-10-10 22:14:57,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:57,368 INFO L225 Difference]: With dead ends: 197 [2024-10-10 22:14:57,368 INFO L226 Difference]: Without dead ends: 110 [2024-10-10 22:14:57,369 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 123 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=111, Invalid=351, Unknown=0, NotChecked=0, Total=462 [2024-10-10 22:14:57,369 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 32 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 256 SdHoareTripleChecker+Invalid, 227 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:57,369 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 256 Invalid, 227 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:57,370 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-10-10 22:14:57,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 110. [2024-10-10 22:14:57,400 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 93 states have (on average 1.1935483870967742) internal successors, (111), 92 states have internal predecessors, (111), 9 states have call successors, (9), 5 states have call predecessors, (9), 7 states have return successors, (13), 12 states have call predecessors, (13), 9 states have call successors, (13) [2024-10-10 22:14:57,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 133 transitions. [2024-10-10 22:14:57,401 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 133 transitions. Word has length 64 [2024-10-10 22:14:57,401 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:57,401 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 133 transitions. [2024-10-10 22:14:57,401 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 19 states have internal predecessors, (58), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-10 22:14:57,402 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 133 transitions. [2024-10-10 22:14:57,402 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-10-10 22:14:57,402 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:57,402 INFO L215 NwaCegarLoop]: trace histogram [9, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-10 22:14:57,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:57,603 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:57,603 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:57,604 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:57,604 INFO L85 PathProgramCache]: Analyzing trace with hash -2146777757, now seen corresponding path program 2 times [2024-10-10 22:14:57,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:57,604 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1544299629] [2024-10-10 22:14:57,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:57,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:57,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,754 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-10 22:14:57,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,756 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-10-10 22:14:57,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,759 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 32 [2024-10-10 22:14:57,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,761 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-10 22:14:57,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,763 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-10-10 22:14:57,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:14:57,765 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 15 proven. 32 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-10-10 22:14:57,765 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-10 22:14:57,765 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1544299629] [2024-10-10 22:14:57,765 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1544299629] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-10 22:14:57,766 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1513418705] [2024-10-10 22:14:57,766 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-10 22:14:57,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:57,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:57,768 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:57,769 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-10-10 22:14:57,853 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-10 22:14:57,853 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-10 22:14:57,856 INFO L255 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-10 22:14:57,858 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:14:57,934 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 25 proven. 30 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2024-10-10 22:14:57,935 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:14:58,028 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 17 proven. 30 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-10-10 22:14:58,028 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1513418705] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-10 22:14:58,029 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-10 22:14:58,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2024-10-10 22:14:58,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [697127621] [2024-10-10 22:14:58,029 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-10 22:14:58,029 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-10 22:14:58,029 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-10 22:14:58,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-10 22:14:58,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2024-10-10 22:14:58,030 INFO L87 Difference]: Start difference. First operand 110 states and 133 transitions. Second operand has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-10-10 22:14:58,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-10 22:14:58,130 INFO L93 Difference]: Finished difference Result 114 states and 136 transitions. [2024-10-10 22:14:58,130 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-10 22:14:58,130 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 68 [2024-10-10 22:14:58,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-10 22:14:58,131 INFO L225 Difference]: With dead ends: 114 [2024-10-10 22:14:58,131 INFO L226 Difference]: Without dead ends: 103 [2024-10-10 22:14:58,132 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 135 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=77, Invalid=195, Unknown=0, NotChecked=0, Total=272 [2024-10-10 22:14:58,132 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-10 22:14:58,132 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 85 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-10 22:14:58,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-10-10 22:14:58,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 98. [2024-10-10 22:14:58,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 81 states have (on average 1.1975308641975309) internal successors, (97), 80 states have internal predecessors, (97), 9 states have call successors, (9), 5 states have call predecessors, (9), 7 states have return successors, (13), 12 states have call predecessors, (13), 9 states have call successors, (13) [2024-10-10 22:14:58,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 119 transitions. [2024-10-10 22:14:58,161 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 119 transitions. Word has length 68 [2024-10-10 22:14:58,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-10 22:14:58,161 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 119 transitions. [2024-10-10 22:14:58,161 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.642857142857143) internal successors, (51), 14 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-10-10 22:14:58,161 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 119 transitions. [2024-10-10 22:14:58,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-10-10 22:14:58,162 INFO L207 NwaCegarLoop]: Found error trace [2024-10-10 22:14:58,162 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 3, 3, 3, 3, 3, 3, 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] [2024-10-10 22:14:58,176 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-10-10 22:14:58,366 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-10-10 22:14:58,367 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-10 22:14:58,367 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-10 22:14:58,367 INFO L85 PathProgramCache]: Analyzing trace with hash 986345860, now seen corresponding path program 7 times [2024-10-10 22:14:58,367 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-10 22:14:58,367 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [497825343] [2024-10-10 22:14:58,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-10 22:14:58,367 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-10 22:14:58,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-10 22:14:58,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1949337972] [2024-10-10 22:14:58,399 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-10-10 22:14:58,399 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-10 22:14:58,400 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-10 22:14:58,401 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-10 22:14:58,403 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-10 22:15:00,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-10 22:15:00,026 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 125 conjuncts are in the unsatisfiable core [2024-10-10 22:15:00,031 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-10 22:15:00,053 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-10-10 22:15:00,073 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 18 [2024-10-10 22:15:00,100 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,101 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 28 [2024-10-10 22:15:00,223 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,223 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 38 [2024-10-10 22:15:00,262 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,263 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 10 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 40 treesize of output 48 [2024-10-10 22:15:00,312 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,312 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 15 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 47 treesize of output 58 [2024-10-10 22:15:00,467 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,467 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 21 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 54 treesize of output 68 [2024-10-10 22:15:00,557 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,558 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 28 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 21 case distinctions, treesize of input 61 treesize of output 78 [2024-10-10 22:15:00,663 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-10-10 22:15:00,663 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 36 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 28 case distinctions, treesize of input 68 treesize of output 88 [2024-10-10 22:15:01,937 INFO L349 Elim1Store]: treesize reduction 324, result has 16.5 percent of original size [2024-10-10 22:15:01,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 36 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 54 case distinctions, treesize of input 91 treesize of output 104 [2024-10-10 22:15:03,060 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 8 proven. 150 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-10 22:15:03,060 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-10 22:15:11,889 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1217 treesize of output 1199 [2024-10-10 22:15:15,640 INFO L349 Elim1Store]: treesize reduction 50, result has 78.4 percent of original size [2024-10-10 22:15:15,659 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input -4317422871412919181 treesize of output -4317422871412919001