Add regex support in policy schema

components/policy/core/common/schema.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/policy/core/common/schema.h"
 
 #include <algorithm>
 #include <climits>
 #include <map>
 #include <utility>
-#include <vector>
 
 #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;
 
 namespace policy {
 
 using internal::PropertiesNode;
 using internal::PropertyNode;
 using internal::RestrictionNode;
 using internal::SchemaData;
 using internal::SchemaNode;
@@ skipping 138 matching lines @@
   }
 
   const int* int_enums(int index) const {
     return schema_data_.int_enums + index;
   }
 
   const char** string_enums(int index) const {
     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;
+
  private:
   friend class base::RefCountedThreadSafe<InternalStorage>;
 
   InternalStorage();
   ~InternalStorage();
 
   // Determines the expected |sizes| of the storage for the representation
   // of |schema|.
   static void DetermineStorageSizes(const base::DictionaryValue& schema,
                                    StorageSizes* sizes);
@@ skipping 33 matching lines @@
 
   bool ParseEnum(const base::DictionaryValue& schema,
                  base::Value::Type type,
                  SchemaNode* schema_node,
                  std::string* error);
 
   bool ParseRangedInt(const base::DictionaryValue& schema,
                        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.
   static bool ResolveReferences(const IdMap& id_map,
                                 const ReferenceList& reference_list,
                                 std::string* error);
 
+  // Cache for CompileRegex(), will memorize return value of every call to
+  // CompileRegex() and return results directly next time.
+  mutable std::map<std::string, re2::RE2*> regex_cache_;
+  STLValueDeleter<std::map<std::string, re2::RE2*> > regex_cache_deleter_;
+
   SchemaData schema_data_;
   std::vector<std::string> strings_;
   std::vector<SchemaNode> schema_nodes_;
   std::vector<PropertyNode> property_nodes_;
   std::vector<PropertiesNode> properties_nodes_;
   std::vector<RestrictionNode> restriction_nodes_;
   std::vector<int> int_enums_;
   std::vector<const char*> string_enums_;
 
   DISALLOW_COPY_AND_ASSIGN(InternalStorage);
 };
 
-Schema::InternalStorage::InternalStorage() {}
+Schema::InternalStorage::InternalStorage()
+    : regex_cache_deleter_(&regex_cache_) {}
 
 Schema::InternalStorage::~InternalStorage() {}
 
 // static
 scoped_refptr<const Schema::InternalStorage> Schema::InternalStorage::Wrap(
     const SchemaData* data) {
   InternalStorage* storage = new InternalStorage();
   storage->schema_data_.schema_nodes = data->schema_nodes;
   storage->schema_data_.property_nodes = data->property_nodes;
   storage->schema_data_.properties_nodes = data->properties_nodes;
@@ skipping 56 matching lines @@
   SchemaData* data = &storage->schema_data_;
   data->schema_nodes = vector_as_array(&storage->schema_nodes_);
   data->property_nodes = vector_as_array(&storage->property_nodes_);
   data->properties_nodes = vector_as_array(&storage->properties_nodes_);
   data->restriction_nodes = vector_as_array(&storage->restriction_nodes_);
   data->int_enums = vector_as_array(&storage->int_enums_);
   data->string_enums = vector_as_array(&storage->string_enums_);
   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,
     StorageSizes* sizes) {
   std::string ref_string;
   if (schema.GetString(schema::kRef, &ref_string)) {
     // Schemas with a "$ref" attribute don't take additional storage.
     return;
   }
 
@@ skipping 22 matching lines @@
     if (schema.GetDictionary(schema::kProperties, &properties)) {
       for (base::DictionaryValue::Iterator it(*properties);
            !it.IsAtEnd(); it.Advance()) {
         // This should have been verified by the JSONSchemaValidator.
         CHECK(it.value().GetAsDictionary(&dict));
         DetermineStorageSizes(*dict, sizes);
         sizes->strings++;
         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)) {
       if (type == base::Value::TYPE_INTEGER) {
         sizes->int_enums += possible_values->GetSize();
       } else if (type == base::Value::TYPE_STRING) {
         sizes->string_enums += possible_values->GetSize();
         sizes->strings += possible_values->GetSize();
       }
       sizes->restriction_nodes++;
     }
   } 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++;
+      sizes->restriction_nodes++;
+    }
   }
 }
 
 bool Schema::InternalStorage::Parse(const base::DictionaryValue& schema,
                                     int* index,
                                     IdMap* id_map,
                                     ReferenceList* reference_list,
                                     std::string* error) {
   std::string ref_string;
   if (schema.GetString(schema::kRef, &ref_string)) {
@@ skipping 26 matching lines @@
 
   if (type == base::Value::TYPE_DICTIONARY) {
     if (!ParseDictionary(schema, schema_node, id_map, reference_list, error))
       return false;
   } else if (type == base::Value::TYPE_LIST) {
     if (!ParseList(schema, schema_node, id_map, reference_list, error))
       return false;
   } 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) {
       *error = "Only integers can have minimum and maximum";
       return false;
     }
     if (!ParseRangedInt(schema, schema_node, error))
       return false;
   }
   std::string id_string;
   if (schema.GetString(schema::kId, &id_string)) {
     if (ContainsKey(*id_map, id_string)) {
       *error = "Duplicated id: " + id_string;
       return false;
     }
     (*id_map)[id_string] = *index;
   }
 
   return true;
 }
 
 bool Schema::InternalStorage::ParseDictionary(
     const base::DictionaryValue& schema,
     SchemaNode* schema_node,
     IdMap* id_map,
     ReferenceList* reference_list,
     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;
 
   const base::DictionaryValue* dict = NULL;
   if (schema.GetDictionary(schema::kAdditionalProperties, &dict)) {
     if (!Parse(*dict, &properties_nodes_[extra].additional,
                id_map, reference_list, error)) {
       return false;
     }
   }
 
+  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
+    // This and below reserves nodes for all of the |properties|, and makes sure
+    // they are contiguous. Recursive calls to Parse() will append after these
     // elements.
-    property_nodes_.resize(base_index + properties->size());
+    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.
       CHECK(it.value().GetAsDictionary(&dict));
       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>(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));
+      re2::RE2* compiled_regex = CompileRegex(it.key());
+      if (!compiled_regex->ok()) {
+        *error =
+            "/" + it.key() + "/ is a invalid regex: " + compiled_regex->error();
+        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;
 }
 
 bool Schema::InternalStorage::ParseList(const base::DictionaryValue& schema,
                                         SchemaNode* schema_node,
                                         IdMap* id_map,
                                         ReferenceList* reference_list,
                                         std::string* error) {
@@ skipping 71 matching lines @@
     *error = "Invalid range restriction for int type.";
     return false;
   }
   schema_node->extra = static_cast<int>(restriction_nodes_.size());
   restriction_nodes_.push_back(RestrictionNode());
   restriction_nodes_.back().ranged_restriction.max_value = max_value;
   restriction_nodes_.back().ranged_restriction.min_value = min_value;
   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;
+  }
+  re2::RE2* compiled_regex = CompileRegex(pattern);
+  if (!compiled_regex->ok()) {
+    *error = "/" + pattern + "/ is invalid regex: " + compiled_regex->error();
+    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,
     const ReferenceList& reference_list,
     std::string* error) {
   for (ReferenceList::const_iterator ref = reference_list.begin();
        ref != reference_list.end(); ++ref) {
     IdMap::const_iterator id = id_map.find(ref->first);
     if (id == id_map.end()) {
       *error = "Invalid $ref: " + ref->first;
@@ skipping 85 matching lines @@
     return false;
   }
 
   const base::DictionaryValue* dict = NULL;
   const base::ListValue* list = NULL;
   int int_value;
   std::string str_value;
   if (value.GetAsDictionary(&dict)) {
     for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
          it.Advance()) {
-      Schema subschema = GetProperty(it.key());
-      if (!subschema.valid()) {
+      SchemaList schema_list = GetMatchingProperties(it.key());
+      if (schema_list.empty()) {
         // Unknown property was detected.
         SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
         if (!StrategyAllowUnknownOnTopLevel(strategy))
           return false;
-      } else if (!subschema.Validate(it.value(),
-                                     StrategyForNextLevel(strategy),
-                                     error_path,
-                                     error)) {
-        // Invalid property was detected.
-        AddDictKeyPrefixToPath(it.key(), error_path);
-        if (!StrategyAllowInvalidOnTopLevel(strategy))
-          return false;
+      } else {
+        for (SchemaList::iterator subschema = schema_list.begin();
+             subschema != schema_list.end(); ++subschema) {
+          if (!subschema->Validate(it.value(),
+                                   StrategyForNextLevel(strategy),
+                                   error_path,
+                                   error)) {
+            // Invalid property was detected.
+            AddDictKeyPrefixToPath(it.key(), error_path);
+            if (!StrategyAllowInvalidOnTopLevel(strategy))
+              return false;
+          }
+        }
       }
     }
   } else if (value.GetAsList(&list)) {
     for (base::ListValue::const_iterator it = list->begin(); it != list->end();
          ++it) {
       if (!*it ||
           !GetItems().Validate(**it,
                                StrategyForNextLevel(strategy),
                                error_path,
                                error)) {
@@ skipping 42 matching lines @@
         error_path, error, "The value type doesn't match the schema type.");
     return false;
   }
 
   base::DictionaryValue* dict = NULL;
   base::ListValue* list = NULL;
   if (value->GetAsDictionary(&dict)) {
     std::vector<std::string> drop_list;  // Contains the keys to drop.
     for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
          it.Advance()) {
-      Schema subschema = GetProperty(it.key());
-      if (!subschema.valid()) {
+      SchemaList schema_list = GetMatchingProperties(it.key());
+      if (schema_list.empty()) {
         // Unknown property was detected.
         SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
         if (StrategyAllowUnknownOnTopLevel(strategy))
           drop_list.push_back(it.key());
         else
           return false;
       } else {
-        base::Value* sub_value = NULL;
-        dict->GetWithoutPathExpansion(it.key(), &sub_value);
-        if (!subschema.Normalize(sub_value,
-                                 StrategyForNextLevel(strategy),
-                                 error_path,
-                                 error,
-                                 changed)) {
-          // Invalid property was detected.
-          AddDictKeyPrefixToPath(it.key(), error_path);
-          if (StrategyAllowInvalidOnTopLevel(strategy))
-            drop_list.push_back(it.key());
-          else
-            return false;
+        for (SchemaList::iterator subschema = schema_list.begin();
+             subschema != schema_list.end(); ++subschema) {
+          base::Value* sub_value = NULL;
+          dict->GetWithoutPathExpansion(it.key(), &sub_value);
+          if (!subschema->Normalize(sub_value,
+                                    StrategyForNextLevel(strategy),
+                                    error_path,
+                                    error,
+                                    changed)) {
+            // Invalid property was detected.
+            AddDictKeyPrefixToPath(it.key(), error_path);
+            if (StrategyAllowInvalidOnTopLevel(strategy)) {
+              drop_list.push_back(it.key());
+              break;
+            } else {
+              return false;
+            }
+          }
         }
       }
     }
     if (changed && !drop_list.empty())
       *changed = true;
     for (std::vector<std::string>::const_iterator it = drop_list.begin();
          it != drop_list.end();
          ++it) {
       dict->RemoveWithoutPathExpansion(*it, NULL);
     }
@@ skipping 94 matching lines @@
 
 Schema Schema::GetAdditionalProperties() const {
   CHECK(valid());
   CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
   const PropertiesNode* node = storage_->properties(node_->extra);
   if (node->additional == kInvalid)
     return Schema();
   return Schema(storage_, storage_->schema(node->additional));
 }
 
+SchemaList Schema::GetPatternProperties(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);
+  SchemaList matching_properties;
+  for (const PropertyNode* it = begin; it != end; ++it) {
+    if (re2::RE2::PartialMatch(key, *storage_->CompileRegex(it->key))) {
+      matching_properties.push_back(
+          Schema(storage_, storage_->schema(it->schema)));
+    }
+  }
+  return matching_properties;
+}
+
 Schema Schema::GetProperty(const std::string& key) const {
   Schema schema = GetKnownProperty(key);
-  return schema.valid() ? schema : GetAdditionalProperties();
+  if (schema.valid())
+    return schema;
+  return GetAdditionalProperties();
+}
+
+SchemaList Schema::GetMatchingProperties(const std::string& key) const {
+  SchemaList schema_list;
+
+  Schema known_property = GetKnownProperty(key);
+  if (known_property.valid())
+    schema_list.push_back(known_property);
+
+  SchemaList pattern_properties = GetPatternProperties(key);
+  schema_list.insert(
+      schema_list.end(), pattern_properties.begin(), pattern_properties.end());
+
+  if (schema_list.empty()) {
+    Schema additional_property = GetAdditionalProperties();
+    if (additional_property.valid())
+      schema_list.push_back(additional_property);
+  }
+
+  return schema_list;
 }
 
 Schema Schema::GetItems() const {
   CHECK(valid());
   CHECK_EQ(base::Value::TYPE_LIST, type());
   if (node_->extra == kInvalid)
     return Schema();
   return Schema(storage_, storage_->schema(node_->extra));
 }
 
 bool Schema::ValidateIntegerRestriction(int index, int value) const {
   const RestrictionNode* rnode = storage_->restriction(index);
   if (rnode->ranged_restriction.min_value <=
       rnode->ranged_restriction.max_value) {
     return rnode->ranged_restriction.min_value <= value &&
            rnode->ranged_restriction.max_value >= value;
   } else {
     for (int i = rnode->enumeration_restriction.offset_begin;
-         i < rnode->enumeration_restriction.offset_end; i++) {
+         i < rnode->enumeration_restriction.offset_end; ++i) {
       if (*storage_->int_enums(i) == value)
         return true;
     }
     return false;
   }
 }
 
 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) {
+      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