Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java	(revision 6644)
+++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Condition.java	(revision 6645)
@@ -16,4 +16,5 @@
 import org.openstreetmap.josm.gui.mappaint.Environment;
 import org.openstreetmap.josm.tools.CheckParameterUtil;
+import org.openstreetmap.josm.tools.Predicate;
 import org.openstreetmap.josm.tools.Predicates;
 import org.openstreetmap.josm.tools.Utils;
@@ -26,5 +27,7 @@
         switch (context) {
         case PRIMITIVE:
-            return new KeyValueCondition(k, v, op, considerValAsKey);
+            return KeyValueRegexpCondition.SUPPORTED_OPS.contains(op) && !considerValAsKey
+                    ? new KeyValueRegexpCondition(k, v, op, false)
+                    : new KeyValueCondition(k, v, op, considerValAsKey);
         case LINK:
             if (considerValAsKey)
@@ -180,4 +183,25 @@
         public String toString() {
             return "[" + k + "'" + op + "'" + v + "]";
+        }
+    }
+
+    public static class KeyValueRegexpCondition extends KeyValueCondition {
+
+        public final Pattern pattern;
+        public static final EnumSet<Op> SUPPORTED_OPS = EnumSet.of(Op.REGEX, Op.NREGEX);
+
+        public KeyValueRegexpCondition(String k, String v, Op op, boolean considerValAsKey) {
+            super(k, v, op, considerValAsKey);
+            CheckParameterUtil.ensureThat(!considerValAsKey, "considerValAsKey is not supported");
+            CheckParameterUtil.ensureThat(SUPPORTED_OPS.contains(op), "Op must be REGEX or NREGEX");
+            this.pattern = Pattern.compile(v);
+        }
+
+        @Override
+        public boolean applies(Environment env) {
+            final String value = env.osm.get(k);
+            return value != null && (op.equals(Op.REGEX)
+                    ? pattern.matcher(value).find()
+                    : !pattern.matcher(value).find());
         }
     }
@@ -244,4 +268,5 @@
         public final boolean negateResult;
         public final KeyMatchType matchType;
+        public Predicate<String> containsPattern;
 
         public KeyCondition(String label, boolean negateResult, KeyMatchType matchType){
@@ -249,4 +274,7 @@
             this.negateResult = negateResult;
             this.matchType = matchType;
+            this.containsPattern = KeyMatchType.REGEX.equals(matchType)
+                    ? Predicates.stringContainsPattern(Pattern.compile(label))
+                    : null;
         }
 
@@ -259,8 +287,9 @@
                 else if (KeyMatchType.FALSE.equals(matchType))
                     return e.osm.isKeyFalse(label) ^ negateResult;
-                else if (KeyMatchType.REGEX.equals(matchType))
-                    return Utils.exists(e.osm.keySet(), Predicates.stringContainsPattern(Pattern.compile(label))) ^ negateResult;
-                else
+                else if (KeyMatchType.REGEX.equals(matchType)) {
+                    return Utils.exists(e.osm.keySet(), containsPattern) ^ negateResult;
+                } else {
                     return e.osm.hasKey(label) ^ negateResult;
+                }
             case LINK:
                 Utils.ensure(false, "Illegal state: KeyCondition not supported in LINK context");