// Copyright (c) 2012 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 "extensions/common/url_pattern_set.h"

#include <algorithm>
#include <iterator>

#include "base/logging.h"
#include "base/memory/linked_ptr.h"
#include "base/stl_util.h"
#include "base/values.h"
#include "content/public/common/url_constants.h"
#include "extensions/common/error_utils.h"
#include "extensions/common/url_pattern.h"
#include "url/gurl.h"

namespace extensions {

namespace {

const char kInvalidURLPatternError[] = "Invalid url pattern '*'";

}  // namespace

// static
void URLPatternSet::CreateDifference(const URLPatternSet& set1,
                                     const URLPatternSet& set2,
                                     URLPatternSet* out) {
  out->ClearPatterns();
  out->patterns_ = base::STLSetDifference<std::set<URLPattern> >(
      set1.patterns_, set2.patterns_);
}

// static
void URLPatternSet::CreateIntersection(const URLPatternSet& set1,
                                       const URLPatternSet& set2,
                                       URLPatternSet* out) {
  out->ClearPatterns();
  std::set_intersection(set1.patterns_.begin(), set1.patterns_.end(),
                        set2.patterns_.begin(), set2.patterns_.end(),
                        std::inserter<std::set<URLPattern> >(
                            out->patterns_, out->patterns_.begin()));
}

// static
void URLPatternSet::CreateUnion(const URLPatternSet& set1,
                                const URLPatternSet& set2,
                                URLPatternSet* out) {
  out->ClearPatterns();
  std::set_union(set1.patterns_.begin(), set1.patterns_.end(),
                 set2.patterns_.begin(), set2.patterns_.end(),
                 std::inserter<std::set<URLPattern> >(
                     out->patterns_, out->patterns_.begin()));
}

// static
void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets,
                                URLPatternSet* out) {
  out->ClearPatterns();
  if (sets.empty())
    return;

  // N-way union algorithm is basic O(nlog(n)) merge algorithm.
  //
  // Do the first merge step into a working set so that we don't mutate any of
  // the input.
  std::vector<URLPatternSet> working;
  for (size_t i = 0; i < sets.size(); i += 2) {
    if (i + 1 < sets.size()) {
      URLPatternSet u;
      URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u);
      working.push_back(u);
    } else {
      working.push_back(sets[i]);
    }
  }

  for (size_t skip = 1; skip < working.size(); skip *= 2) {
    for (size_t i = 0; i < (working.size() - skip); i += skip) {
      URLPatternSet u;
      URLPatternSet::CreateUnion(working[i], working[i + skip], &u);
      working[i].patterns_.swap(u.patterns_);
    }
  }

  out->patterns_.swap(working[0].patterns_);
}

URLPatternSet::URLPatternSet() {}

URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
    : patterns_(rhs.patterns_) {}

URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
    : patterns_(patterns) {}

URLPatternSet::~URLPatternSet() {}

URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
  patterns_ = rhs.patterns_;
  return *this;
}

bool URLPatternSet::operator==(const URLPatternSet& other) const {
  return patterns_ == other.patterns_;
}

bool URLPatternSet::is_empty() const {
  return patterns_.empty();
}

size_t URLPatternSet::size() const {
  return patterns_.size();
}

bool URLPatternSet::AddPattern(const URLPattern& pattern) {
  return patterns_.insert(pattern).second;
}

void URLPatternSet::AddPatterns(const URLPatternSet& set) {
  patterns_.insert(set.patterns().begin(),
                   set.patterns().end());
}

void URLPatternSet::ClearPatterns() {
  patterns_.clear();
}

bool URLPatternSet::Contains(const URLPatternSet& other) const {
  for (URLPatternSet::const_iterator it = other.begin();
       it != other.end(); ++it) {
    if (!ContainsPattern(*it))
      return false;
  }

  return true;
}

bool URLPatternSet::ContainsPattern(const URLPattern& pattern) const {
  for (URLPatternSet::const_iterator it = begin();
       it != end(); ++it) {
    if (it->Contains(pattern))
      return true;
  }
  return false;
}

bool URLPatternSet::MatchesURL(const GURL& url) const {
  for (URLPatternSet::const_iterator pattern = patterns_.begin();
       pattern != patterns_.end(); ++pattern) {
    if (pattern->MatchesURL(url))
      return true;
  }

  return false;
}

bool URLPatternSet::MatchesSecurityOrigin(const GURL& origin) const {
  for (URLPatternSet::const_iterator pattern = patterns_.begin();
       pattern != patterns_.end(); ++pattern) {
    if (pattern->MatchesSecurityOrigin(origin))
      return true;
  }

  return false;
}

bool URLPatternSet::OverlapsWith(const URLPatternSet& other) const {
  // Two extension extents overlap if there is any one URL that would match at
  // least one pattern in each of the extents.
  for (URLPatternSet::const_iterator i = patterns_.begin();
       i != patterns_.end(); ++i) {
    for (URLPatternSet::const_iterator j = other.patterns().begin();
         j != other.patterns().end(); ++j) {
      if (i->OverlapsWith(*j))
        return true;
    }
  }

  return false;
}

scoped_ptr<base::ListValue> URLPatternSet::ToValue() const {
  scoped_ptr<ListValue> value(new ListValue);
  for (URLPatternSet::const_iterator i = patterns_.begin();
       i != patterns_.end(); ++i)
    value->AppendIfNotPresent(Value::CreateStringValue(i->GetAsString()));
  return value.Pass();
}

bool URLPatternSet::Populate(const std::vector<std::string>& patterns,
                             int valid_schemes,
                             bool allow_file_access,
                             std::string* error) {
  ClearPatterns();
  for (size_t i = 0; i < patterns.size(); ++i) {
    URLPattern pattern(valid_schemes);
    if (pattern.Parse(patterns[i]) != URLPattern::PARSE_SUCCESS) {
      if (error) {
        *error = ErrorUtils::FormatErrorMessage(kInvalidURLPatternError,
                                                patterns[i]);
      } else {
        LOG(ERROR) << "Invalid url pattern: " << patterns[i];
      }
      return false;
    }
    if (!allow_file_access && pattern.MatchesScheme(chrome::kFileScheme)) {
      pattern.SetValidSchemes(
          pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
    }
    AddPattern(pattern);
  }
  return true;
}

bool URLPatternSet::Populate(const base::ListValue& value,
                             int valid_schemes,
                             bool allow_file_access,
                             std::string* error) {
  std::vector<std::string> patterns;
  for (size_t i = 0; i < value.GetSize(); ++i) {
    std::string item;
    if (!value.GetString(i, &item))
      return false;
    patterns.push_back(item);
  }
  return Populate(patterns, valid_schemes, allow_file_access, error);
}

}  // namespace extensions