Add regex support in policy schema

components/policy/core/common/schema.cc

Index: components/policy/core/common/schema.cc
diff --git a/components/policy/core/common/schema.cc b/components/policy/core/common/schema.cc
index d50bd8abc4d031cd8c445f32e5cb0626f5d8ad84..f624123c68840b99597f38cfb284ac6d330c2f47 100644
--- a/components/policy/core/common/schema.cc
+++ b/components/policy/core/common/schema.cc
@@ -12,11 +12,14 @@
 
 #include "base/compiler_specific.h"
 #include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/memory/scoped_vector.h"
+#include "base/stl_util.h"
 #include "base/strings/stringprintf.h"
 #include "components/json_schema/json_schema_constants.h"
 #include "components/json_schema/json_schema_validator.h"
 #include "components/policy/core/common/schema_internal.h"
+#include "third_party/re2/re2/re2.h"
 
 namespace schema = json_schema_constants;
 
@@ -175,6 +178,10 @@ class Schema::InternalStorage
     return schema_data_.string_enums + index;
   }
 
+  // Compiles regular expression |pattern|. The result is cached and will be
+  // returned directly next time.
+  re2::RE2* CompileRegex(const std::string &pattern) const;

[Joao da Silva, 2014/03/21 12:58:12]

const std::string& pattern

[binjin, 2014/03/27 17:57:47]

Done.

+
  private:
   friend class base::RefCountedThreadSafe<InternalStorage>;
 
@@ -228,6 +235,10 @@ class Schema::InternalStorage
                        SchemaNode* schema_node,
                        std::string* error);
 
+  bool ParseStringPattern(const base::DictionaryValue& schema,
+                          SchemaNode* schema_node,
+                          std::string* error);
+
   // Assigns the IDs in |id_map| to the pending references in the
   // |reference_list|. If an ID is missing then |error| is set and false is
   // returned; otherwise returns true.
@@ -235,6 +246,9 @@ class Schema::InternalStorage
                                 const ReferenceList& reference_list,
                                 std::string* error);
 
+  mutable std::map<std::string, re2::RE2*> regex_cache_;

[Joao da Silva, 2014/03/21 12:58:12]

Argh, mutable. I think it's better than complicating this; please document why
we use it though.

[binjin, 2014/03/27 17:57:47]

Done.

+  STLValueDeleter<std::map<std::string, re2::RE2*> > cache_deleter_;
+
   SchemaData schema_data_;
   std::vector<std::string> strings_;
   std::vector<SchemaNode> schema_nodes_;
@@ -247,7 +261,7 @@ class Schema::InternalStorage
   DISALLOW_COPY_AND_ASSIGN(InternalStorage);
 };
 
-Schema::InternalStorage::InternalStorage() {}
+Schema::InternalStorage::InternalStorage() : cache_deleter_(&regex_cache_) {}
 
 Schema::InternalStorage::~InternalStorage() {}
 
@@ -324,6 +338,17 @@ Schema::InternalStorage::ParseSchema(const base::DictionaryValue& schema,
   return storage;
 }
 
+re2::RE2* Schema::InternalStorage::CompileRegex(
+    const std::string& pattern) const {
+  std::map<std::string, re2::RE2*>::iterator it = regex_cache_.find(pattern);
+  if (it == regex_cache_.end()) {
+    re2::RE2* compiled = new re2::RE2(pattern);
+    regex_cache_[pattern] = compiled;
+    return compiled;
+  }
+  return it->second;
+}
+
 // static
 void Schema::InternalStorage::DetermineStorageSizes(
     const base::DictionaryValue& schema,
@@ -366,6 +391,17 @@ void Schema::InternalStorage::DetermineStorageSizes(
         sizes->property_nodes++;
       }
     }
+
+    const base::DictionaryValue* pattern_properties = NULL;
+    if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties)) {
+      for (base::DictionaryValue::Iterator it(*pattern_properties);
+           !it.IsAtEnd(); it.Advance()) {
+        CHECK(it.value().GetAsDictionary(&dict));
+        DetermineStorageSizes(*dict, sizes);
+        sizes->strings++;
+        sizes->property_nodes++;
+      }
+    }
   } else if (schema.HasKey(schema::kEnum)) {
     const base::ListValue* possible_values = NULL;
     if (schema.GetList(schema::kEnum, &possible_values)) {
@@ -380,6 +416,12 @@ void Schema::InternalStorage::DetermineStorageSizes(
   } else if (type == base::Value::TYPE_INTEGER) {
     if (schema.HasKey(schema::kMinimum) || schema.HasKey(schema::kMaximum))
       sizes->restriction_nodes++;
+  } else if (type == base::Value::TYPE_STRING) {
+    if (schema.HasKey(schema::kPattern)) {
+      sizes->strings++;
+      sizes->string_enums ++;

[Joao da Silva, 2014/03/21 12:58:12]

nit: remove space before ++

[binjin, 2014/03/27 17:57:47]

Done.

+      sizes->restriction_nodes++;
+    }
   }
 }
 
@@ -426,6 +468,9 @@ bool Schema::InternalStorage::Parse(const base::DictionaryValue& schema,
   } else if (schema.HasKey(schema::kEnum)) {
     if (!ParseEnum(schema, type, schema_node, error))
       return false;
+  } else if (schema.HasKey(schema::kPattern)) {
+    if (!ParseStringPattern(schema, schema_node, error))
+      return false;
   } else if (schema.HasKey(schema::kMinimum) ||
              schema.HasKey(schema::kMaximum)) {
     if (type != base::Value::TYPE_INTEGER) {
@@ -455,8 +500,6 @@ bool Schema::InternalStorage::ParseDictionary(
     std::string* error) {
   int extra = static_cast<int>(properties_nodes_.size());
   properties_nodes_.push_back(PropertiesNode());
-  properties_nodes_[extra].begin = kInvalid;
-  properties_nodes_[extra].end = kInvalid;
   properties_nodes_[extra].additional = kInvalid;
   schema_node->extra = extra;
 
@@ -468,15 +511,25 @@ bool Schema::InternalStorage::ParseDictionary(
     }
   }
 
+  properties_nodes_[extra].begin = static_cast<int>(property_nodes_.size());
+
   const base::DictionaryValue* properties = NULL;
-  if (schema.GetDictionary(schema::kProperties, &properties)) {
-    int base_index = static_cast<int>(property_nodes_.size());
-    // This reserves nodes for all of the |properties|, and makes sure they
-    // are contiguous. Recursive calls to Parse() will append after these
-    // elements.

[Joao da Silva, 2014/03/21 12:58:12]

Please leave this comment included.

[binjin, 2014/03/27 17:57:47]

Done.

-    property_nodes_.resize(base_index + properties->size());
+  if (schema.GetDictionary(schema::kProperties, &properties))
+    property_nodes_.resize(property_nodes_.size() + properties->size());
+
+  properties_nodes_[extra].end = static_cast<int>(property_nodes_.size());
+
+  const base::DictionaryValue* pattern_properties = NULL;
+  if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties))
+    property_nodes_.resize(property_nodes_.size() + pattern_properties->size());
 
+  properties_nodes_[extra].pattern_end =
+      static_cast<int>(property_nodes_.size());
+
+  if (properties != NULL) {
+    int base_index = properties_nodes_[extra].begin;
     int index = base_index;
+
     for (base::DictionaryValue::Iterator it(*properties);
          !it.IsAtEnd(); it.Advance(), ++index) {
       // This should have been verified by the JSONSchemaValidator.
@@ -489,8 +542,33 @@ bool Schema::InternalStorage::ParseDictionary(
       }
     }
     CHECK_EQ(static_cast<int>(properties->size()), index - base_index);
-    properties_nodes_[extra].begin = base_index;
-    properties_nodes_[extra].end = index;
+  }
+
+  if (pattern_properties != NULL) {
+    int base_index = properties_nodes_[extra].end;
+    int index = base_index;
+
+    for (base::DictionaryValue::Iterator it(*pattern_properties);
+         !it.IsAtEnd(); it.Advance(), ++index) {
+      CHECK(it.value().GetAsDictionary(&dict));
+      if (!CompileRegex(it.key())->ok()) {
+        *error = "Invalid regex: /" + it.key() + "/.";

[Joao da Silva, 2014/03/21 12:58:12]

Include the ->error()

[binjin, 2014/03/27 17:57:47]

Done.

+        return false;
+      }
+      strings_.push_back(it.key());
+      property_nodes_[index].key = strings_.back().c_str();
+      if (!Parse(*dict, &property_nodes_[index].schema,
+                 id_map, reference_list, error)) {
+        return false;
+      }
+    }
+    CHECK_EQ(static_cast<int>(pattern_properties->size()), index - base_index);
+  }
+
+  if (properties_nodes_[extra].begin == properties_nodes_[extra].pattern_end) {
+    properties_nodes_[extra].begin = kInvalid;
+    properties_nodes_[extra].end = kInvalid;
+    properties_nodes_[extra].pattern_end = kInvalid;
   }
 
   return true;
@@ -582,6 +660,30 @@ bool Schema::InternalStorage::ParseRangedInt(
   return true;
 }
 
+bool Schema::InternalStorage::ParseStringPattern(
+    const base::DictionaryValue& schema,
+    SchemaNode* schema_node,
+    std::string* error) {
+  std::string pattern;
+  if (!schema.GetString(schema::kPattern, &pattern)) {
+    *error = "Schema pattern must be a string.";
+    return false;
+  }
+  if (!CompileRegex(pattern)->ok()) {
+    *error = "Invalid regex: /" + pattern + "/.";

[Joao da Silva, 2014/03/21 12:58:12]

Include the ->error() in this message too

[binjin, 2014/03/27 17:57:47]

Done.

+    return false;
+  }
+  int index = static_cast<int>(string_enums_.size());
+  strings_.push_back(pattern);
+  string_enums_.push_back(strings_.back().c_str());
+  schema_node->extra = static_cast<int>(restriction_nodes_.size());
+  restriction_nodes_.push_back(RestrictionNode());
+  restriction_nodes_.back().string_pattern_restriction.pattern_index = index;
+  restriction_nodes_.back().string_pattern_restriction.pattern_index_backup =
+      index;
+  return true;
+}
+
 // static
 bool Schema::InternalStorage::ResolveReferences(
     const IdMap& id_map,
@@ -899,9 +1001,30 @@ Schema Schema::GetAdditionalProperties() const {
   return Schema(storage_, storage_->schema(node->additional));
 }
 
+Schema Schema::GetPatternProperty(const std::string& key) const {
+  CHECK(valid());
+  CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
+  const PropertiesNode* node = storage_->properties(node_->extra);
+  const PropertyNode* begin = storage_->property(node->end);
+  const PropertyNode* end = storage_->property(node->pattern_end);
+  for (const PropertyNode* it = begin; it != end; ++it) {
+    if (re2::RE2::PartialMatch(key, *storage_->CompileRegex(begin->key)))

[Joao da Silva, 2014/03/21 12:58:12]

begin->key should be it->key

[binjin, 2014/03/27 17:57:47]

Done.

+      return Schema(storage_, storage_->schema(it->schema));
+  }
+  return Schema();
+}
+
 Schema Schema::GetProperty(const std::string& key) const {

[Joao da Silva, 2014/03/21 12:58:12]

So this method is just a helper to mix GetKnownProperty() and
GetAdditionalProperties(), and it doesn't really work with
GetPatternProperties() once that changes to return a list of matching schemas.

I think this method should stay as is, but Validate() and Normalize() need to
handle GetPatternProperties() correctly.

[binjin, 2014/04/01 12:29:36]

I deprecated this function, as it's a little bit confusing since
PatternProperties was introduced.

   Schema schema = GetKnownProperty(key);
-  return schema.valid() ? schema : GetAdditionalProperties();
+  if (schema.valid())
+    return schema;
+  // This is slightly different from json schema standard. We won't match the
+  // key against "patternProperty" regular expressions if it's already
+  // presented by "property" attribute.
+  schema = GetPatternProperty(key);
+  if (schema.valid())
+    return schema;
+  return GetAdditionalProperties();
 }
 
 Schema Schema::GetItems() const {
@@ -930,12 +1053,20 @@ bool Schema::ValidateIntegerRestriction(int index, int value) const {
 
 bool Schema::ValidateStringRestriction(int index, const char* str) const {
   const RestrictionNode* rnode = storage_->restriction(index);
-  for (int i = rnode->enumeration_restriction.offset_begin;
-       i < rnode->enumeration_restriction.offset_end; i++) {
-    if (strcmp(*storage_->string_enums(i), str) == 0)
-      return true;
+  if (rnode->enumeration_restriction.offset_begin <
+      rnode->enumeration_restriction.offset_end) {
+    for (int i = rnode->enumeration_restriction.offset_begin;
+        i < rnode->enumeration_restriction.offset_end; i++) {

[Joao da Silva, 2014/03/21 12:58:12]

nit: add one space at the beginning of this line

[binjin, 2014/03/27 17:57:47]

Done.

+      if (strcmp(*storage_->string_enums(i), str) == 0)
+        return true;
+    }
+    return false;
+  } else {
+    int index = rnode->string_pattern_restriction.pattern_index;
+    DCHECK(index == rnode->string_pattern_restriction.pattern_index_backup);
+    re2::RE2* regex = storage_->CompileRegex(*storage_->string_enums(index));
+    return re2::RE2::PartialMatch(str, *regex);
   }
-  return false;
 }
 
 }  // namespace policy