Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java	(revision 6546)
+++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java	(revision 6547)
@@ -6,5 +6,4 @@
 import java.text.MessageFormat;
 import java.util.EnumSet;
-import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 
@@ -16,4 +15,5 @@
 import org.openstreetmap.josm.gui.mappaint.Cascade;
 import org.openstreetmap.josm.gui.mappaint.Environment;
+import org.openstreetmap.josm.tools.Predicates;
 import org.openstreetmap.josm.tools.Utils;
 
@@ -39,11 +39,11 @@
     }
 
-    public static Condition create(String k, boolean not, boolean yes, boolean no, Context context) {
+    public static Condition create(String k, boolean not, KeyMatchType matchType, Context context) {
         switch (context) {
         case PRIMITIVE:
-            return new KeyCondition(k, not, yes, no);
+            return new KeyCondition(k, not, matchType);
         case LINK:
-            if (yes || no)
-                throw new MapCSSException("Question mark operator ''?'' not supported in LINK context");
+            if (matchType != null)
+                throw new MapCSSException("Question mark operator ''?'' and regexp match not supported in LINK context");
             if (not)
                 return new RoleCondition(k, Op.NEQ);
@@ -77,7 +77,6 @@
             case REGEX:
             case NREGEX:
-                Pattern p = Pattern.compile(prototypeString);
-                Matcher m = p.matcher(testString);
-                return REGEX.equals(this) ? m.find() : !m.find();
+                final boolean contains = Pattern.compile(prototypeString).matcher(testString).find();
+                return REGEX.equals(this) ? contains : !contains;
             case ONE_OF:
                 String[] parts = testString.split(";");
@@ -142,7 +141,7 @@
     public static class KeyValueCondition extends Condition {
 
-        public String k;
-        public String v;
-        public Op op;
+        public final String k;
+        public final String v;
+        public final Op op;
 
         /**
@@ -175,6 +174,6 @@
 
     public static class RoleCondition extends Condition {
-        public String role;
-        public Op op;
+        public final String role;
+        public final Op op;
 
         public RoleCondition(String role, Op op) {
@@ -192,6 +191,6 @@
 
     public static class IndexCondition extends Condition {
-        public String index;
-        public Op op;
+        public final String index;
+        public final Op op;
 
         public IndexCondition(String index, Op op) {
@@ -205,4 +204,8 @@
             return op.eval(Integer.toString(env.index + 1), index);
         }
+    }
+
+    public static enum KeyMatchType {
+        EQ, TRUE, FALSE, REGEX
     }
 
@@ -228,14 +231,12 @@
     public static class KeyCondition extends Condition {
 
-        private String label;
-        private boolean negateResult;
-        private boolean testForTrueValues;
-        private boolean testForFalseValues;
-
-        public KeyCondition(String label, boolean negateResult, boolean testForTrueValues, boolean testForFalseValues){
+        public final String label;
+        public final boolean negateResult;
+        public final KeyMatchType matchType;
+
+        public KeyCondition(String label, boolean negateResult, KeyMatchType matchType){
             this.label = label;
             this.negateResult = negateResult;
-            this.testForTrueValues = testForTrueValues;
-            this.testForFalseValues = testForFalseValues;
+            this.matchType = matchType;
         }
 
@@ -244,8 +245,10 @@
             switch(e.getContext()) {
             case PRIMITIVE:
-                if (testForTrueValues)
+                if (KeyMatchType.TRUE.equals(matchType))
                     return OsmUtils.isTrue(e.osm.get(label)) ^ negateResult;
-                else if (testForFalseValues)
+                else if (KeyMatchType.FALSE.equals(matchType))
                     return OsmUtils.isFalse(e.osm.get(label)) ^ negateResult;
+                else if (KeyMatchType.REGEX.equals(matchType))
+                    return Utils.exists(e.osm.keySet(), Predicates.stringContainsPattern(Pattern.compile(label))) ^ negateResult;
                 else
                     return e.osm.hasKey(label) ^ negateResult;
@@ -269,6 +272,6 @@
     public static class PseudoClassCondition extends Condition {
 
-        String id;
-        boolean not;
+        public final String id;
+        public final boolean not;
 
         public PseudoClassCondition(String id, boolean not) {
Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSParser.jj
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSParser.jj	(revision 6546)
+++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSParser.jj	(revision 6547)
@@ -345,14 +345,17 @@
 {
     boolean not = false;
-    boolean yes = false;
-    boolean no = false;
+    Condition.KeyMatchType matchType = null;;
     String key;
 }
 {
     ( <EXCLAMATION> { not = true; } )?
-    key=tag_key()
-    ( LOOKAHEAD(2) <QUESTION> <EXCLAMATION> { no = true; } )?
-    ( <QUESTION> { yes = true; } )?
-    { return Condition.create(key, not, yes, no, context); }
+    (
+        { matchType = Condition.KeyMatchType.REGEX; } key = regex()
+    |
+        key = tag_key()
+    )
+    ( LOOKAHEAD(2) <QUESTION> <EXCLAMATION> { matchType = Condition.KeyMatchType.FALSE; } )?
+    (              <QUESTION>               { matchType = Condition.KeyMatchType.TRUE;  } )?
+    { return Condition.create(key, not, matchType, context); }
 }
 
Index: trunk/src/org/openstreetmap/josm/tools/Predicates.java
===================================================================
--- trunk/src/org/openstreetmap/josm/tools/Predicates.java	(revision 6547)
+++ trunk/src/org/openstreetmap/josm/tools/Predicates.java	(revision 6547)
@@ -0,0 +1,48 @@
+package org.openstreetmap.josm.tools;
+
+import java.util.regex.Pattern;
+
+/**
+ * Utility class for creating {@link Predicate}s.
+ */
+public final class Predicates {
+
+    private Predicates() {
+    }
+
+    /**
+     * Returns a {@link Predicate} executing {@link Pattern#matcher(CharSequence)} and {@link java.util.regex.Matcher#matches}.
+     */
+    public static Predicate<String> stringMatchesPattern(final Pattern pattern) {
+        return new Predicate<String>() {
+            @Override
+            public boolean evaluate(String string) {
+                return pattern.matcher(string).matches();
+            }
+        };
+    }
+
+    /**
+     * Returns a {@link Predicate} executing {@link Pattern#matcher(CharSequence)} and {@link java.util.regex.Matcher#find}.
+     */
+    public static Predicate<String> stringContainsPattern(final Pattern pattern) {
+        return new Predicate<String>() {
+            @Override
+            public boolean evaluate(String string) {
+                return pattern.matcher(string).find();
+            }
+        };
+    }
+
+    /**
+     * Returns a {@link Predicate} executing {@link String#contains(CharSequence)}.
+     */
+    public static Predicate<String> stringContains(final String pattern) {
+        return new Predicate<String>() {
+            @Override
+            public boolean evaluate(String string) {
+                return string.contains(pattern);
+            }
+        };
+    }
+}