changeset 3:fdc263e5806b

added inverse matching in StringSetMatcher. Since this is not easy to do in regexes, it's at the next hight level in StringSetMatcher added a optional CG accessor interface (geChoice(i), getAllChoices(), getProcessedChoices() getUnprocessedChoices()) that can be used from listeners and peers to enumerate/analyse choice sets. Note that not all CGs have to support this as there is no requirement that CGs actually use pre-computed choice sets. The low level accessor is getChoice(i), ChoiceGeneratorBase provides generic (not very efficient) set accessor implementations. Note that ChoiceGeneratorBase.getChoice() has to be overridden in subclasses in order to support choice enumeration, the default impl is just there so that we don't break subclass compilation
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Tue, 03 Feb 2015 08:49:33 -0800
parents b920e6b1be83
children d0a0ff1c0e10
files src/main/gov/nasa/jpf/util/StringSetMatcher.java src/main/gov/nasa/jpf/util/event/EventChoiceGenerator.java src/main/gov/nasa/jpf/vm/BooleanChoiceGenerator.java src/main/gov/nasa/jpf/vm/ChoiceGenerator.java src/main/gov/nasa/jpf/vm/ChoiceGeneratorBase.java src/main/gov/nasa/jpf/vm/choice/BreakGenerator.java src/main/gov/nasa/jpf/vm/choice/DoubleThresholdGenerator.java src/main/gov/nasa/jpf/vm/choice/IntIntervalGenerator.java src/main/gov/nasa/jpf/vm/choice/InvocationCG.java src/main/gov/nasa/jpf/vm/choice/NumberChoiceFromList.java src/main/gov/nasa/jpf/vm/choice/RandomIntIntervalGenerator.java src/main/gov/nasa/jpf/vm/choice/RandomOrderIntCG.java src/main/gov/nasa/jpf/vm/choice/RandomOrderLongCG.java src/main/gov/nasa/jpf/vm/choice/ThreadChoiceFromSet.java src/main/gov/nasa/jpf/vm/choice/TypedObjectChoice.java src/tests/gov/nasa/jpf/util/StringSetMatcherTest.java
diffstat 16 files changed, 310 insertions(+), 14 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/gov/nasa/jpf/util/StringSetMatcher.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/util/StringSetMatcher.java	Tue Feb 03 08:49:33 2015 -0800
@@ -22,18 +22,23 @@
 
 /**
  * simple utility that can be used to check for string matches in
- * sets with '*' wildcards, e.g. to check for class name lists like
+ * sets with '*' wildcards, e.g. to check for class name lists such as
  *
  *   vm.halt_on_throw=java.lang.reflect.*:my.own.Exception
  *
- * Only meta chars in patterns are '*', i.e. '.' is a regular char to match
+ * Only meta chars in patterns are '*' and '!', i.e. '.' is a regular char to match
+ * A '!' prefix inverts the match
  */
 public class StringSetMatcher {
 
+  public static final char WILDCARD = '*';
+  public static final char INVERTED = '!';
+  
   boolean hasAnyPattern; // do we have a universal '*' pattern?
 
   Pattern[] pattern;
   Matcher[] matcher;
+  boolean[] inverted;
 
   /**
    * convenience method for matcher pairs containing of explicit excludes and
@@ -67,6 +72,7 @@
     int n = set.length;
     pattern = new Pattern[n];
     matcher = new Matcher[n];
+    inverted = new boolean[n];
 
     for (int i=0; i<n; i++){
       String s = set[i];
@@ -79,6 +85,7 @@
         Pattern p =  createPattern(s);
         pattern[i] = p;
         matcher[i] = p.matcher(""); // gets reset upon use
+        inverted[i] = isInverted(s);
       }
     }
   }
@@ -87,7 +94,7 @@
   public String toString() {
     int n=0;
     StringBuilder sb = new StringBuilder(64);
-    sb.append("StringSetMatcher [regex_patterns=");
+    sb.append("StringSetMatcher {patterns=");
 
     if (hasAnyPattern) {
       sb.append(".*");
@@ -99,16 +106,20 @@
         if (n++>0) {
           sb.append(',');
         }
+        if (inverted[i]){
+          sb.append(INVERTED);
+        }
         sb.append(pattern[i]);
       }
     }
-    sb.append(']');
+    sb.append('}');
     return sb.toString();
   }
 
   public void addPattern (String s){
 
     if (s.equals("*")) { // no need to compile
+      // note that this doesn't include the - pointless - "!*", which would match nothing
       hasAnyPattern = true;
 
     } else {
@@ -122,18 +133,33 @@
       System.arraycopy(matcher, 0, mNew, 0, n);
       mNew[n] = pNew[n].matcher("");
 
+      boolean[] iNew = new boolean[pNew.length];
+      System.arraycopy( inverted, 0, iNew, 0, n);
+      iNew[n] = isInverted(s);
+      
       pattern = pNew;
       matcher = mNew;
+      inverted = iNew;
     }
   }
 
-  Pattern createPattern (String s){
+  public static boolean isInverted (String s){
+    return (!s.isEmpty() && s.charAt(0) == INVERTED);
+  }
+  
+  protected Pattern createPattern (String s){
     Pattern p;
+    int j = 0;
+    int len = s.length();
 
+    // inversion is better done outside of regex
+    if ((len > 0) && s.charAt(0) == INVERTED){
+      j++; // skip INVERTED char
+    }
+    
     StringBuilder sb = new StringBuilder();
-
-    int len = s.length();
-    for (int j=0; j<len; j++){
+        
+    for (; j<len; j++){
       char c = s.charAt(j);
       switch (c){
       case '.' : sb.append("\\."); break;
@@ -165,7 +191,7 @@
         Matcher m = matcher[i];
         m.reset(s);
 
-        if (m.matches()){
+        if (m.matches() != inverted[i]){
           return true;
         }
       }
@@ -179,17 +205,23 @@
    */
   public boolean matchesAll (String s){
     if (s != null) {
-      if (hasAnyPattern && pattern.length == 1) {
+      if (hasAnyPattern && pattern.length == 1) { // there might be other patterns
         return true; // no need to check
       }
 
       for (int i=0; i<pattern.length; i++){
         Pattern p = pattern[i];
-        Matcher m = matcher[i];
-        m.reset(s);
+        if (p != null){
+          Matcher m = matcher[i];
+          m.reset(s);
 
-        if (!m.matches()){
-          return false;
+          if (m.matches() == inverted[i]){
+            return false;
+          }
+        } else {
+          if (inverted[i]){
+            return false;
+          }
         }
       }
 
--- a/src/main/gov/nasa/jpf/util/event/EventChoiceGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/util/event/EventChoiceGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -57,6 +57,24 @@
     this.ctx = ctx;
   }
   
+  @Override
+  public Event getChoice (int idx){
+    if (idx >= 0){
+      Event e = base;
+      for (int i=0; i<idx; i++){
+        e = e.alt;
+        if (e == null){
+          break;
+        } else {
+          return e;
+        }
+      }
+      
+    }
+    throw new IllegalArgumentException("choice index out of range: " + idx);
+  }
+
+  
   public void setContextExpander (EventContext ctx){
     this.ctx = ctx;
   }
--- a/src/main/gov/nasa/jpf/vm/BooleanChoiceGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/BooleanChoiceGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -74,6 +74,17 @@
       next = !next;
     }
   }
+  
+  @Override
+  public Boolean getChoice (int idx){
+    if (idx == 0){
+      return falseFirst ? Boolean.FALSE : Boolean.TRUE;
+    } else if (idx == 1){
+      return falseFirst ? Boolean.TRUE : Boolean.FALSE;      
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
 
   @Override
   public void reset () {
--- a/src/main/gov/nasa/jpf/vm/ChoiceGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/ChoiceGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -67,6 +67,15 @@
 
   int getProcessedNumberOfChoices();
 
+  
+  // choice getters. Note that not all CGs need to support them since
+  // there is no requirement that CGs compute finite choice sets upon creation
+  
+  T getChoice(int i);
+  T[] getAllChoices();
+  T[] getProcessedChoices();
+  T[] getUnprocessedChoices();
+  
   ChoiceGenerator<?> getPreviousChoiceGenerator();
 
   int getNumberOfParents();
--- a/src/main/gov/nasa/jpf/vm/ChoiceGeneratorBase.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/ChoiceGeneratorBase.java	Tue Feb 03 08:49:33 2015 -0800
@@ -335,6 +335,67 @@
     setDone();
   }
 
+  // override this to support explicit CG enumeration from listeners etc.
+  
+  /**
+   * explicit choice enumeration. Override if supported
+   * @return choice value or null if not supported
+   */
+  @Override
+  public T getChoice (int idx){
+    return null;
+  }
+  
+  //--- generic choice set getter implementation
+  // Note - this requires an overloaded getChoice() and can be very slow (depending on CG implementation)
+  
+  @Override
+  public T[] getAllChoices(){
+    int n = getTotalNumberOfChoices();
+    T[] a = (T[]) new Object[n];
+    for (int i=0; i<n; i++){
+      T c = getChoice(i);
+      if (c == null){
+        return null; // CG doesn't support choice enumeration
+      } else {
+        a[i] = c;
+      }
+    }
+    return a;
+  }
+  
+  @Override
+  public T[] getProcessedChoices(){
+    int n = getProcessedNumberOfChoices();
+    T[] a = (T[]) new Object[n];
+    for (int i=0; i<n; i++){
+      T c = getChoice(i);
+      if (c == null){
+        return null; // CG doesn't support choice enumeration
+      } else {
+        a[i] = c;
+      }
+    }
+    return a;    
+  }
+  
+  @Override
+  public T[] getUnprocessedChoices(){
+    int n = getTotalNumberOfChoices();
+    int m = getProcessedNumberOfChoices();
+    T[] a = (T[]) new Object[n];
+    for (int i=m-1; i<n; i++){
+      T c = getChoice(i);
+      if (c == null){
+        return null; // CG doesn't support choice enumeration
+      } else {
+        a[i] = c;
+      }
+    }
+    return a;    
+  }
+  
+  
   @Override
   public boolean isDone() {
     return isDone;
--- a/src/main/gov/nasa/jpf/vm/choice/BreakGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/BreakGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -49,6 +49,15 @@
   }
 
   @Override
+  public ThreadInfo getChoice (int idx){
+    if (idx == 0){
+      return ti;
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+  
+  @Override
   public void printOn (PrintWriter pw) {
     pw.println("BreakGenerator {" + ti.getName() + "}");
   }
--- a/src/main/gov/nasa/jpf/vm/choice/DoubleThresholdGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/DoubleThresholdGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -40,6 +40,15 @@
   }
 
   @Override
+  public Double getChoice (int idx){
+    if (idx >= 0 && idx < 3){
+      return values[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+  
+  @Override
   public void reset () {
     count = -1;
 
--- a/src/main/gov/nasa/jpf/vm/choice/IntIntervalGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/IntIntervalGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -95,6 +95,16 @@
   }
 
   @Override
+  public Integer getChoice (int idx){
+    int nChoices = getTotalNumberOfChoices();
+    if (idx >= 0 && idx < nChoices){
+      return min + idx*delta;
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+  
+  @Override
   public Integer getNextChoice () {
     return new Integer(next);
   }
--- a/src/main/gov/nasa/jpf/vm/choice/InvocationCG.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/InvocationCG.java	Tue Feb 03 08:49:33 2015 -0800
@@ -44,6 +44,15 @@
   }
   
   @Override
+  public Invocation getChoice (int idx){
+    if (idx >=0 && idx < invokes.size()){
+      return invokes.get(idx);
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+  
+  @Override
   public void advance () {
     cur = it.next();
   }
--- a/src/main/gov/nasa/jpf/vm/choice/NumberChoiceFromList.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/NumberChoiceFromList.java	Tue Feb 03 08:49:33 2015 -0800
@@ -76,6 +76,14 @@
     }
   }
   
+  @Override
+  public T getChoice (int idx){
+    if (idx >=0 && idx < values.length){
+      return values[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
 
   @Override
   public void reset () {
--- a/src/main/gov/nasa/jpf/vm/choice/RandomIntIntervalGenerator.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/RandomIntIntervalGenerator.java	Tue Feb 03 08:49:33 2015 -0800
@@ -72,6 +72,21 @@
     random = new Random(seed);
   }
 
+  @Override
+  public Integer getChoice (int idx){
+    if (idx >= 0 && idx < nChoices){
+      // Ok, this is really not efficient - use only for non-performance critical operations
+      Random r = new Random(seed);
+      int v=0;
+      for (int i=0; i<idx; i++){
+        v = r.nextInt(range);
+      }
+      return v + min;
+      
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
 
   @Override
   public void reset () {
--- a/src/main/gov/nasa/jpf/vm/choice/RandomOrderIntCG.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/RandomOrderIntCG.java	Tue Feb 03 08:49:33 2015 -0800
@@ -47,6 +47,15 @@
   }
 
   @Override
+  public Integer getChoice (int idx){
+    if (idx >= 0 && idx < choices.length){
+      return choices[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+  
+  @Override
   public Integer getNextChoice() {
     return new Integer(choices[nextIdx]);
   }
--- a/src/main/gov/nasa/jpf/vm/choice/RandomOrderLongCG.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/RandomOrderLongCG.java	Tue Feb 03 08:49:33 2015 -0800
@@ -45,6 +45,16 @@
     }
     nextIdx = -1;
   }
+  
+  @Override
+  public Long getChoice (int idx){
+    if (idx >= 0 && idx < choices.length){
+      return choices[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+
 
   @Override
   public Long getNextChoice() {
--- a/src/main/gov/nasa/jpf/vm/choice/ThreadChoiceFromSet.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/ThreadChoiceFromSet.java	Tue Feb 03 08:49:33 2015 -0800
@@ -59,6 +59,16 @@
   }
   
   @Override
+  public ThreadInfo getChoice (int idx){
+    if (idx >= 0 && idx < values.length){
+      return values[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+
+  
+  @Override
   public void reset () {
     count = -1;
 
--- a/src/main/gov/nasa/jpf/vm/choice/TypedObjectChoice.java	Sat Jan 24 18:19:08 2015 -0800
+++ b/src/main/gov/nasa/jpf/vm/choice/TypedObjectChoice.java	Tue Feb 03 08:49:33 2015 -0800
@@ -73,6 +73,16 @@
   }
   
   @Override
+  public Integer getChoice (int idx){
+    if (idx >= 0 && idx < values.length){
+      return values[idx];
+    } else {
+      throw new IllegalArgumentException("choice index out of range: " + idx);
+    }
+  }
+
+  
+  @Override
   public void advance () {
     count++;
   }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tests/gov/nasa/jpf/util/StringSetMatcherTest.java	Tue Feb 03 08:49:33 2015 -0800
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2015, United States Government, as represented by the
+ * Administrator of the National Aeronautics and Space Administration.
+ * All rights reserved.
+ *
+ * The Java Pathfinder core (jpf-core) platform is licensed under the
+ * Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ * 
+ *        http://www.apache.org/licenses/LICENSE-2.0. 
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and 
+ * limitations under the License.
+ */
+package gov.nasa.jpf.util;
+
+import gov.nasa.jpf.util.test.TestJPF;
+import org.junit.Test;
+
+/**
+ * regression test for .util.StringSetMatcher
+ */
+public class StringSetMatcherTest extends TestJPF {
+ 
+  @Test
+  public void testInversion (){
+    StringSetMatcher ssm = new StringSetMatcher("!failure-*", "failure-10");
+    
+    assertTrue( ssm.matchesAny("blah"));
+    assertFalse( ssm.matchesAny("failure-0"));
+    
+    assertTrue( ssm.matchesAny("failure-10"));
+    assertFalse( ssm.matchesAll("failure-10"));
+  }
+  
+  @Test
+  public void testMatchesAll (){
+    StringSetMatcher ssm = new StringSetMatcher("a*", "*blah");
+    
+    assertTrue( ssm.matchesAll("aXXblah"));
+    assertFalse( ssm.matchesAll("xblah"));
+  }
+  
+  @Test
+  public void testMatchesAny (){
+    StringSetMatcher ssm = new StringSetMatcher("blah", "gna");
+    
+    assertTrue( ssm.matchesAny("blah"));
+    assertFalse( ssm.matchesAny("xblah"));
+  }
+
+  @Test
+  public void testHasAnyPattern(){
+    StringSetMatcher ssm = new StringSetMatcher("*", "gna");
+    assertTrue( ssm.matchesAny("blubb"));
+    assertTrue( ssm.matchesAll("gna"));
+    
+    ssm = new StringSetMatcher("*");  // single pattern optimization
+    assertTrue(ssm.matchesAll("gna"));
+    assertTrue(ssm.matchesAny("gulp"));
+  }
+  
+}