src/main/gov/nasa/jpf/search/DFSearch.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.search;
  19
  20
  21 import gov.nasa.jpf.Config;
  22 import gov.nasa.jpf.vm.VM;
  23
  24
  25 /**
  26  * standard depth first model checking (but can be bounded by search depth
  27  * and/or explicit Verify.ignoreIf)
  28  */
  29 public class DFSearch extends Search {
  30
  31   public DFSearch (Config config, VM vm) {
  32         super(config,vm);
  33   }
  34
  35   @Override
  36   public boolean requestBacktrack () {
  37     doBacktrack = true;
  38
  39     return true;
  40   }
  41
  42   /**
  43    * state model of the search
  44    *    next new  -> action
  45    *     T    T      forward
  46    *     T    F      backtrack, forward
  47    *     F    T      backtrack, forward
  48    *     F    F      backtrack, forward
  49    *
  50    * end condition
  51    *    backtrack failed (no saved states)
  52    *  | property violation (currently only checked in new states)
  53    *  | search constraint (depth or memory or time)
  54    *
  55    * <2do> we could split the properties into forward and backtrack properties,
  56    * the latter ones being usable for liveness properties that are basically
  57    * condition accumulators for sub-paths of the state space, to be checked when
  58    * we backtrack to the state where they were introduced.
  59    */
  60   @Override
  61   public void search () {
  62     boolean depthLimitReached = false;
  63
  64     depth = 0;
  65
  66     notifySearchStarted();
  67
  68     while (!done) {
  69       if (checkAndResetBacktrackRequest() || !isNewState() || isEndState() || isIgnoredState() || depthLimitReached ) {
  70         if (!backtrack()) { // backtrack not possible, done
  71           break;
  72         }
  73
  74         depthLimitReached = false;
  75         depth--;
  76         notifyStateBacktracked();
  77       }
  78
  79       if (forward()) {
  80         depth++;
  81         notifyStateAdvanced();
  82
  83         if (currentError != null){
  84           notifyPropertyViolated();
  85
  86           if (hasPropertyTermination()) {
  87             break;
  88           }
  89           // for search.multiple_errors we go on and treat this as a new state
  90           // but hasPropertyTermination() will issue a backtrack request
  91         }
  92
  93         if (depth >= depthLimit) {
  94           depthLimitReached = true;
  95           notifySearchConstraintHit("depth limit reached: " + depthLimit);
  96           continue;
  97         }
  98
  99         if (!checkStateSpaceLimit()) {
 100           notifySearchConstraintHit("memory limit reached: " + minFreeMemory);
 101           // can't go on, we exhausted our memory
 102           break;
 103         }
 104
 105       } else { // forward did not execute any instructions
 106         notifyStateProcessed();
 107       }
 108     }
 109
 110     notifySearchFinished();
 111   }
 112
 113
 114   @Override
 115   public boolean supportsBacktrack () {
 116     return true;
 117   }
 118 }