Changeset 4819

Timestamp:

Oct 4, 2015, 4:59:28 PM (2 years ago)

Author:

nmedfort

Message:

First stage of CC_NameMap removal

Location:

icGREP/icgrep-devel/icgrep

Files:

• UCD/ucd_compiler.cpp (modified) (1 diff)
• cc/cc_namemap.cpp (modified) (2 diffs)
• re/re_compiler.cpp (modified) (1 diff)
• re/re_dictionary.cpp (deleted)
• re/re_memoizer.hpp (moved) (moved from icGREP/icgrep-devel/icgrep/re/re_dictionary.h) (1 diff)
• re/re_name.h (modified) (4 diffs)
• re/re_parser.cpp (modified) (20 diffs)
• re/re_parser.h (modified) (5 diffs)
• toolchain.cpp (modified) (1 diff)
• utf8_encoder.h (modified) (1 diff)

icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp

@@ -2 +2 @@
 #include <cc/cc_compiler.h>
 #include <UCD/unicode_set.h>
+#include <re/re_name.h>
 #include <utf8_encoder.h>
 

icGREP/icgrep-devel/icgrep/cc/cc_namemap.cpp

@@ -9 +9 @@
 #include <re/re_assertion.h>
 #include <UCD/resolve_properties.h>
+#include <re/printer_re.h>
 
 using namespace re;
@@ -61 +62 @@
             return f->second;
         }
-        return insert(std::move(classname), (type == ByteClass) ? makeByteName(classname, cc) : makeName(classname, cc));
+        return insert(std::move(classname), makeName(classname, cc));
     }
     return re;

icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

@@ -18 +18 @@
 #include <re/re_assertion.h>
 #include <re/re_analysis.h>
+#include <re/printer_re.h>
 #include <cc/cc_namemap.hpp>
 #include <pablo/codegenstate.h>

icGREP/icgrep-devel/icgrep/re/re_memoizer.hpp

@@ -2 +2 @@
 #define RE_NAMEDICTIONARY_H
 
+#include <re/re_name.h>
+#include <set>
+
 namespace re {
 
-class NameDictionary
-{
-public:
-    NameDictionary();
+namespace {
+
+struct MemoizerComparator {
+    inline bool operator() (const RE * lh, const RE * rh) const{
+        if (LLVM_LIKELY(isa<Name>(lh) && isa<Name>(rh))) {
+            return *cast<Name>(lh) < *cast<Name>(rh);
+        } else if (isa<Name>(lh)) {
+            return *cast<Name>(lh) < *cast<CC>(rh);
+        }
+        return !(*cast<Name>(rh) < *cast<CC>(lh));
+    }
+};
+
+}
+
+struct Memoizer : private std::set<RE *, MemoizerComparator> {
+
+    inline Name * memoize(CC * cc) {
+        auto f = find(cc);
+        if (f != end()) {
+            return cast<Name>(*f);
+        } else {
+            Name * name = makeName(cc->canonicalName(CC_type::UnicodeClass), cc);
+            insert(name);
+            return name;
+        }
+    }
+
+    inline Name * memoize(Name * name) {
+        return cast<Name>(*insert(name).first);
+    }
 };
 

icGREP/icgrep-devel/icgrep/re/re_name.h

@@ -5 +5 @@
 #include <re/re_cc.h>
 #include <string>
-#include <re/printer_re.h>
 
 namespace pablo {
@@ -43 +42 @@
         mCompiled = var;
     }
+    bool operator<(const Name & other) const;
+    bool operator<(const CC & other) const;
     void setDefinition(RE * definition);
     virtual ~Name() {}
 protected:
     friend Name * makeName(const std::string &, RE *);
-    friend Name * makeByteName(const std::string &, RE *);
     friend Name * makeName(const std::string &, const Type);
     friend Name * makeName(const std::string &, const std::string &, const Type);
@@ -106 +106 @@
 }
 
+inline bool Name::operator < (const Name & other) const {
+    if (mDefinition && other.mDefinition && isa<CC>(mDefinition) && isa<CC>(other.mDefinition)) {
+        return *cast<CC>(mDefinition) < *cast<CC>(other.mDefinition);
+    } else if (mNamespaceLength < other.mNamespaceLength) {
+        return true;
+    } else if (mNamespaceLength > other.mNamespaceLength) {
+        return false;
+    } else if (mNameLength < other.mNameLength) {
+        return true;
+    } else if (mNameLength > other.mNameLength) {
+        return false;
+    }
+    const auto diff = std::memcmp(mNamespace, other.mNamespace, mNamespaceLength);
+    if (diff < 0) {
+        return true;
+    } else if (diff > 0) {
+        return false;
+    }
+    return (std::memcmp(mName, other.mName, mNameLength) < 0);
+}
+
+inline bool Name::operator < (const CC & other) const {
+    if (mDefinition && isa<CC>(mDefinition)) {
+        return *cast<CC>(mDefinition) < other;
+    }
+    return false;
+}
+
 inline Name * makeName(const std::string & name, const Name::Type type) {
     return new Name(nullptr, 0, name.c_str(), name.length(), type, nullptr);
@@ -125 +153 @@
 }
 
-inline Name * makeByteName(const std::string & name, RE * cc) {
-    if (isa<Name>(cc)) {
-        return cast<Name>(cc);
-    }
-    else {
-        return new Name(nullptr, 0, name.c_str(), name.length(), Name::Type::Byte, cc);
-    }
-}
-
 }
 

icGREP/icgrep-devel/icgrep/re/re_parser.cpp

@@ -137 +137 @@
             case ']':
                 if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
-                    return build_CC(parse_utf8_codepoint());
+                    return createCC(parse_utf8_codepoint());
                 }
                 else throw ParseFailure("Use  \\] for literal ].");
@@ -145 +145 @@
                 }
                 else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
-                    return build_CC(parse_utf8_codepoint());
+                    return createCC(parse_utf8_codepoint());
                 }
                 else throw ParseFailure("Use \\} for literal }.");
@@ -158 +158 @@
                 return parse_escaped();
             default:
-                return build_CC(parse_utf8_codepoint());
+                return createCC(parse_utf8_codepoint());
         }
     }
@@ -383 +383 @@
       return parseEscapedSet();
     else
-      return build_CC(parse_escaped_codepoint());
+      return createCC(parse_escaped_codepoint());
 }
 
@@ -495 +495 @@
 }
 
-Name * RE_Parser::parsePropertyExpression() {
+RE * RE_Parser::parsePropertyExpression() {
     const cursor_t start = _cursor;
     while (_cursor != _end && *_cursor != '}' and *_cursor != ':' and *_cursor != '=') {
@@ -513 +513 @@
 }
 
-Name * RE_Parser::createName(const std::string value) {
-
-    auto key = std::make_pair("", value);
-    auto f = mNameMap.find(key);
-    if (f != mNameMap.end()) {
-        return f->second;
-    }
-    Name * property = makeName(value, Name::Type::UnicodeProperty);
-    mNameMap.insert(std::make_pair(std::move(key), property));
-    return property;
-}
-
-Name * RE_Parser::createName(const std::string prop, const std::string value) {
-    auto key = std::make_pair(prop, value);
-    auto f = mNameMap.find(key);
-    if (f != mNameMap.end()) {
-        return f->second;
-    }
-    Name * property = makeName(prop, value, Name::Type::UnicodeProperty);
-    mNameMap.insert(std::make_pair(std::move(key), property));
-    return property;
-}
-
-CC * RE_Parser::parseNamePatternExpression(){
-
-    re::ModeFlagSet outerFlags = fModeFlagSet;
+RE * RE_Parser::parseNamePatternExpression(){
+
+    ModeFlagSet outerFlags = fModeFlagSet;
     fModeFlagSet = 1;
 
@@ -554 +531 @@
 
     // Embed the nameRE in ";.*$nameRE" to skip the codepoint field of Uname.txt
-    RE * embedded = makeSeq({re::makeCC(0x3B), re::makeRep(re::makeAny(), 0, Rep::UNBOUNDED_REP), nameRE});
+    RE * embedded = makeSeq({mMemoizer.memoize(makeCC(0x3B)), makeRep(makeAny(), 0, Rep::UNBOUNDED_REP), nameRE});
     Encoding encoding(Encoding::Type::UTF_8, 8);
     embedded = regular_expression_passes(encoding, embedded);
@@ -571 +548 @@
     catch (std::runtime_error e) {
         releaseSlabAllocatorMemory();
-        std::cerr << "Runtime error: " << e.what() << std::endl;
-        exit(1);
+        throw e;
     }
 #ifndef NDEBUG
@@ -586 +562 @@
     void * icgrep_MCptr = engine->getPointerToFunction(nameSearchIR);
     
-    CC * nameSearchResult = nullptr;
+    CC * result = nullptr;
     if (icgrep_MCptr) {
         GrepExecutor grepEngine(icgrep_MCptr);
         grepEngine.setParseCodepointsOption();
         grepEngine.doGrep("../Uname.txt");
-        nameSearchResult = grepEngine.getParsedCodepoints();
-    }
-    
-    //engine->freeMachineCodeForFunction(nameSearchIR); // This function only prints a "not supported" message. Reevaluate with LLVM 3.6.
+        result = grepEngine.getParsedCodepoints();
+    }
     delete engine;
-    return nameSearchResult;
+    return mMemoizer.memoize(result);
 }
 
@@ -672 +646 @@
     // if and only if it appears immediately after the opening [ or [^
     if ( *_cursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
-        cc->insert(']');
+        insert(cc, ']');
         lastItemKind = CodepointItem;
         lastCodepointItem = static_cast<codepoint_t> (']');
@@ -679 +653 @@
     else if ( *_cursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
         ++_cursor;
-        cc->insert('-');
+        insert(cc, '-');
         lastItemKind = CodepointItem;
         lastCodepointItem = static_cast<codepoint_t> ('-');
@@ -694 +668 @@
                     throw ParseFailure("Set operator has no left operand.");
                 }
-                if (cc->begin() != cc->end()) {
-                    subexprs.push_back(cc);
+                if (!cc->empty()) {
+                    subexprs.push_back(mMemoizer.memoize(cc));
                 }
                 RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
@@ -720 +694 @@
                     throw ParseFailure("Set operator has no right operand.");
                 }
-                if (cc->begin() != cc->end()) {
-                    subexprs.push_back(cc);
+                if (!cc->empty()) {
+                    subexprs.push_back(mMemoizer.memoize(cc));
                 }
                 RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
@@ -742 +716 @@
             case posixPropertyOpener: {
                 if (lastItemKind != NoItem) {
-                    if (cc->begin() != cc->end()) subexprs.push_back(cc);
+                    if (!cc->empty()) {
+                        subexprs.push_back(mMemoizer.memoize(cc));
+                    }
                     RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
                     subexprs.clear();
@@ -783 +759 @@
                     throw ParseFailure("Range operator - has illegal left operand.");
                 }
-                cc->insert_range(lastCodepointItem, parse_codepoint());
+                insert_range(cc, lastCodepointItem, parse_codepoint());
                 lastItemKind = RangeItem;
                 break;
             case hyphenChar:
-                cc->insert('-');
+                insert(cc, '-');
                 lastItemKind = CodepointItem;
                 lastCodepointItem = static_cast<codepoint_t> ('-');
                 break;
             case ampChar:
-                cc->insert('&');
+                insert(cc, '&');
                 lastItemKind = CodepointItem;
                 lastCodepointItem = static_cast<codepoint_t> ('&');
@@ -804 +780 @@
                 else {
                     lastCodepointItem = parse_escaped_codepoint();
-                    cc->insert(lastCodepointItem);
+                    insert(cc, lastCodepointItem);
                     lastItemKind = CodepointItem;
                 }
@@ -810 +786 @@
             case emptyOperator:
                 lastCodepointItem = parse_utf8_codepoint();
-                cc->insert(lastCodepointItem);
+                insert(cc, lastCodepointItem);
                 lastItemKind = CodepointItem;
                 break;
@@ -957 +933 @@
 }
 
-CC * RE_Parser::build_CC(codepoint_t cp) {
-    CC * cc = makeCC();
-    CC_add_codepoint(cc, cp);
-    return cc;
-}
-
-void RE_Parser::CC_add_codepoint(CC * cc, codepoint_t cp) {
+inline Name * RE_Parser::createCC(const codepoint_t cp) {
+    CC * cc = nullptr;
+    if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
+        cc = makeCC();
+        caseInsensitiveInsert(cc, cp);
+    } else {
+        cc = makeCC(cp);
+    }
+    return mMemoizer.memoize(cc);
+}
+
+inline void RE_Parser::insert(CC * cc, const codepoint_t cp) {
     if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
         caseInsensitiveInsert(cc, cp);
@@ -971 +952 @@
 }
 
-void RE_Parser::CC_add_range(CC * cc, codepoint_t lo, codepoint_t hi) {
+inline void RE_Parser::insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi) {
     if (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) {
         caseInsensitiveInsertRange(cc, lo, hi);
@@ -995 +976 @@
 }
 
-inline Name * RE_Parser::makeDigitSet() {
+inline RE * RE_Parser::makeDigitSet() {
     return createName("nd");
 }
 
-inline Name * RE_Parser::makeAlphaNumeric() {
+inline RE * RE_Parser::makeAlphaNumeric() {
     return createName("alnum");
 }
 
-inline Name * RE_Parser::makeWhitespaceSet() {
+inline RE * RE_Parser::makeWhitespaceSet() {
     return createName("whitespace");
 }
 
-inline Name * RE_Parser::makeWordSet() {
+inline RE * RE_Parser::makeWordSet() {
     return createName("word");
 }
 
-}
+RE * RE_Parser::createName(const std::string value) {
+    auto key = std::make_pair("", value);
+    auto f = mNameMap.find(key);
+    if (f != mNameMap.end()) {
+        return f->second;
+    }
+    RE * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
+    mNameMap.insert(std::make_pair(std::move(key), property));
+    return property;
+}
+
+RE * RE_Parser::createName(const std::string prop, const std::string value) {
+    auto key = std::make_pair(prop, value);
+    auto f = mNameMap.find(key);
+    if (f != mNameMap.end()) {
+        return f->second;
+    }
+    RE * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
+    mNameMap.insert(std::make_pair(std::move(key), property));
+    return property;
+}
+
+}

icGREP/icgrep-devel/icgrep/re/re_parser.h

@@ -16 +16 @@
 #include <memory>
 #include <map>
-
+#include <re/re_memoizer.hpp>
 
 namespace re {
@@ -43 +43 @@
 private:
 
-    using NameMap = std::map<std::pair<std::string, std::string>, re::Name *>;
+    using NameMap = std::map<std::pair<std::string, std::string>, re::RE *>;
 
-    typedef std::string::const_iterator cursor_t;
+    using cursor_t = std::string::const_iterator;
 
     RE_Parser(const std::string & regular_expression);
@@ -73 +73 @@
     codepoint_t parse_utf8_codepoint();
 
-    Name * parsePropertyExpression();
+    RE * parsePropertyExpression();
 
-    CC * parseNamePatternExpression();
+    RE * parseNamePatternExpression();
 
     RE * makeComplement(RE * s);
     RE * makeWordBoundary();
     RE * makeWordNonBoundary();
-    Name * makeDigitSet();
-    Name * makeAlphaNumeric();
-    Name * makeWhitespaceSet();
-    Name * makeWordSet();
+    RE * makeDigitSet();
+    RE * makeAlphaNumeric();
+    RE * makeWhitespaceSet();
+    RE * makeWordSet();
 
-    Name * createName(const std::string value);
-    Name * createName(const std::string prop, const std::string value);
+    RE * createName(const std::string value);
+    RE * createName(const std::string prop, const std::string value);
 
     CharsetOperatorKind getCharsetOperator();
@@ -103 +103 @@
 
     // CC insertion dependent on case-insensitive flag.
-    CC * build_CC(codepoint_t cp);
-
-    void CC_add_codepoint(CC * cc, codepoint_t cp);
-
-    void CC_add_range(CC * cc, codepoint_t lo, codepoint_t hi);
+    Name * createCC(const codepoint_t cp);
+    void insert(CC * cc, const codepoint_t cp);
+    void insert_range(CC * cc, const codepoint_t lo, const codepoint_t hi);
 
     static std::string canonicalize(const cursor_t begin, const cursor_t end);
@@ -118 +116 @@
     bool                        fNested;
     NameMap                     mNameMap;
+    Memoizer                    mMemoizer;
 };
 

icGREP/icgrep-devel/icgrep/toolchain.cpp

@@ -100 +100 @@
         std::cerr << "RemoveNullableSuffix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     }
-    
-    cc::CC_NameMap nameMap;
-    re_ast = nameMap.process(re_ast, re::UnicodeClass);
-    
-    // std::cerr << "-----------------------------" << std::endl;
-    
-    if (PrintAllREs || PrintNamedREs) {
-        std::cerr << "Namer:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
-        std::cerr << "NameMap:\n" << nameMap.printMap() << std::endl;
-    }
 
     re_ast = re::RE_Simplifier::simplify(re_ast);

icGREP/icgrep-devel/icgrep/utf8_encoder.h

@@ -8 +8 @@
 #define UTF8_ENCODER_H
 
-//Regular Expressions
 #include <re/re_cc.h>
-#include <cc/cc_namemap.hpp>
 
 namespace cc {
-
-class CC_NameMap;
 
 struct UTF8_Encoder {