summaryrefslogtreecommitdiff
path: root/Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp')
-rw-r--r--Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp239
1 files changed, 239 insertions, 0 deletions
diff --git a/Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp b/Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp
new file mode 100644
index 00000000000..dcc02fc6210
--- /dev/null
+++ b/Build/source/libs/icu/icu-src/source/tools/genrb/filterrb.cpp
@@ -0,0 +1,239 @@
+// © 2018 and later: Unicode, Inc. and others.
+// License & terms of use: http://www.unicode.org/copyright.html
+
+#include <iostream>
+#include <stack>
+
+#include "filterrb.h"
+#include "errmsg.h"
+
+
+const char* PathFilter::kEInclusionNames[] = {
+ "INCLUDE",
+ "PARTIAL",
+ "EXCLUDE"
+};
+
+
+ResKeyPath::ResKeyPath() {}
+
+ResKeyPath::ResKeyPath(const std::string& path, UErrorCode& status) {
+ if (path.empty() || path[0] != '/') {
+ std::cerr << "genrb error: path must start with /: " << path << std::endl;
+ status = U_PARSE_ERROR;
+ return;
+ }
+ if (path.length() == 1) {
+ return;
+ }
+ size_t i;
+ size_t j = 0;
+ while (true) {
+ i = j + 1;
+ j = path.find('/', i);
+ std::string key = path.substr(i, j - i);
+ if (key.empty()) {
+ std::cerr << "genrb error: empty subpaths and trailing slashes are not allowed: " << path << std::endl;
+ status = U_PARSE_ERROR;
+ return;
+ }
+ push(key);
+ if (j == std::string::npos) {
+ break;
+ }
+ }
+}
+
+void ResKeyPath::push(const std::string& key) {
+ fPath.push_back(key);
+}
+
+void ResKeyPath::pop() {
+ fPath.pop_back();
+}
+
+const std::list<std::string>& ResKeyPath::pieces() const {
+ return fPath;
+}
+
+std::ostream& operator<<(std::ostream& out, const ResKeyPath& value) {
+ if (value.pieces().empty()) {
+ out << "/";
+ } else for (auto& key : value.pieces()) {
+ out << "/" << key;
+ }
+ return out;
+}
+
+
+PathFilter::~PathFilter() = default;
+
+
+void SimpleRuleBasedPathFilter::addRule(const std::string& ruleLine, UErrorCode& status) {
+ if (ruleLine.empty()) {
+ std::cerr << "genrb error: empty filter rules are not allowed" << std::endl;
+ status = U_PARSE_ERROR;
+ return;
+ }
+ bool inclusionRule = false;
+ if (ruleLine[0] == '+') {
+ inclusionRule = true;
+ } else if (ruleLine[0] != '-') {
+ std::cerr << "genrb error: rules must start with + or -: " << ruleLine << std::endl;
+ status = U_PARSE_ERROR;
+ return;
+ }
+ ResKeyPath path(ruleLine.substr(1), status);
+ addRule(path, inclusionRule, status);
+}
+
+void SimpleRuleBasedPathFilter::addRule(const ResKeyPath& path, bool inclusionRule, UErrorCode& status) {
+ if (U_FAILURE(status)) {
+ return;
+ }
+ fRoot.applyRule(path, path.pieces().begin(), inclusionRule, status);
+}
+
+PathFilter::EInclusion SimpleRuleBasedPathFilter::match(const ResKeyPath& path) const {
+ const Tree* node = &fRoot;
+
+ // defaultResult "bubbles up" the nearest "definite" inclusion/exclusion rule
+ EInclusion defaultResult = INCLUDE;
+ if (node->fIncluded != PARTIAL) {
+ // rules handled here: "+/" and "-/"
+ defaultResult = node->fIncluded;
+ }
+
+ // isLeaf is whether the filter tree can provide no additional information
+ // even if additional subpaths are added to the given key
+ bool isLeaf = false;
+
+ for (auto& key : path.pieces()) {
+ auto child = node->fChildren.find(key);
+ // Leaf case 1: input path descends outside the filter tree
+ if (child == node->fChildren.end()) {
+ if (node->fWildcard) {
+ // A wildcard pattern is present; continue checking
+ node = node->fWildcard.get();
+ } else {
+ isLeaf = true;
+ break;
+ }
+ } else {
+ node = &child->second;
+ }
+ if (node->fIncluded != PARTIAL) {
+ defaultResult = node->fIncluded;
+ }
+ }
+
+ // Leaf case 2: input path exactly matches a filter leaf
+ if (node->isLeaf()) {
+ isLeaf = true;
+ }
+
+ // Always return PARTIAL if we are not at a leaf
+ if (!isLeaf) {
+ return PARTIAL;
+ }
+
+ // If leaf node is PARTIAL, return the default
+ if (node->fIncluded == PARTIAL) {
+ return defaultResult;
+ }
+
+ return node->fIncluded;
+}
+
+
+SimpleRuleBasedPathFilter::Tree::Tree(const Tree& other)
+ : fIncluded(other.fIncluded), fChildren(other.fChildren) {
+ // Note: can't use the default copy assignment because of the std::unique_ptr
+ if (other.fWildcard) {
+ fWildcard.reset(new Tree(*other.fWildcard));
+ }
+}
+
+bool SimpleRuleBasedPathFilter::Tree::isLeaf() const {
+ return fChildren.empty() && !fWildcard;
+}
+
+void SimpleRuleBasedPathFilter::Tree::applyRule(
+ const ResKeyPath& path,
+ std::list<std::string>::const_iterator it,
+ bool inclusionRule,
+ UErrorCode& status) {
+
+ // Base Case
+ if (it == path.pieces().end()) {
+ if (isVerbose() && (fIncluded != PARTIAL || !isLeaf())) {
+ std::cout << "genrb info: rule on path " << path
+ << " overrides previous rules" << std::endl;
+ }
+ fIncluded = inclusionRule ? INCLUDE : EXCLUDE;
+ fChildren.clear();
+ fWildcard.reset();
+ return;
+ }
+
+ // Recursive Step
+ auto& key = *it;
+ if (key == "*") {
+ // Case 1: Wildcard
+ if (!fWildcard) {
+ fWildcard.reset(new Tree());
+ }
+ // Apply the rule to fWildcard and also to all existing children.
+ it++;
+ fWildcard->applyRule(path, it, inclusionRule, status);
+ for (auto& child : fChildren) {
+ child.second.applyRule(path, it, inclusionRule, status);
+ }
+ it--;
+
+ } else {
+ // Case 2: Normal Key
+ auto search = fChildren.find(key);
+ if (search == fChildren.end()) {
+ if (fWildcard) {
+ // Deep-copy the existing wildcard tree into the new key
+ search = fChildren.emplace(key, Tree(*fWildcard)).first;
+ } else {
+ search = fChildren.emplace(key, Tree()).first;
+ }
+ }
+ it++;
+ search->second.applyRule(path, it, inclusionRule, status);
+ it--;
+ }
+}
+
+void SimpleRuleBasedPathFilter::Tree::print(std::ostream& out, int32_t indent) const {
+ for (int32_t i=0; i<indent; i++) out << "\t";
+ out << "included: " << kEInclusionNames[fIncluded] << std::endl;
+ for (auto& child : fChildren) {
+ for (int32_t i=0; i<indent; i++) out << "\t";
+ out << child.first << ": {" << std::endl;
+ child.second.print(out, indent + 1);
+ for (int32_t i=0; i<indent; i++) out << "\t";
+ out << "}" << std::endl;
+ }
+ if (fWildcard) {
+ for (int32_t i=0; i<indent; i++) out << "\t";
+ out << "* {" << std::endl;
+ fWildcard->print(out, indent + 1);
+ for (int32_t i=0; i<indent; i++) out << "\t";
+ out << "}" << std::endl;
+ }
+}
+
+void SimpleRuleBasedPathFilter::print(std::ostream& out) const {
+ out << "SimpleRuleBasedPathFilter {" << std::endl;
+ fRoot.print(out, 1);
+ out << "}" << std::endl;
+}
+
+std::ostream& operator<<(std::ostream& out, const SimpleRuleBasedPathFilter& value) {
+ value.print(out);
+ return out;
+}