Changeset 6141 for icGREP

Timestamp:

Aug 8, 2018, 3:36:26 PM (7 months ago)

Author:

cameron

Message:

Support for searching grapheme clusters in all possible reorderings

Location:

icGREP/icgrep-devel/icgrep/re/Unicode

Files:

• decomposition.cpp (modified) (1 diff)
• decomposition.h (modified) (2 diffs)

icGREP/icgrep-devel/icgrep/re/Unicode/decomposition.cpp

@@ -245 +245 @@
     return re;
 }
+
+/* Reordering of Grapheme Clusters */
+
+/* Extract the next grapheme cluster at a given position within a sequence. */
+
+std::u32string getCluster(Seq * s, unsigned position) {
+    unsigned pos = position;
+    unsigned size = s->size();
+    std::u32string rslt;
+    while ((pos < size) && isa<CC>((*s)[pos])) {
+        CC * cc = cast<CC>((*s)[pos]);
+        if (cc->empty()) return rslt;
+        codepoint_t lo = lo_codepoint(cc->front());
+        codepoint_t hi = hi_codepoint(cc->back());
+        if (lo != hi) // not a singleton CC; end of the cluster.
+            return rslt;
+        if (pos > position) {
+            // After the first codepoint of a cluster, all remaining codepoints
+            // must have ccc > 0.   Terminate the cluster when any starter
+            // (codepoint with ccc==0) is found.
+            const auto & cccObj = cast<EnumeratedPropertyObject>(property_object_table[ccc]);
+            const UnicodeSet & ccc0 = cccObj->GetCodepointSet(CCC_ns::NR);
+            if (ccc0.contains(lo)) return rslt;
+        }
+        rslt.push_back(lo);
+        pos++;
+    }
+    return rslt;
+}
+
+/*  Helper function to insert a given mark at all possible positions within
+    a set of prefixes, subject to constraints on Unicode canonically-equivalent
+    ordering. */
+std::vector<std::u32string> allReorderedInsertions(std::vector<std::u32string> prefixes, codepoint_t mark) {
+    const auto & cccObj = cast<EnumeratedPropertyObject>(property_object_table[ccc]);
+    const UnicodeSet & cccSet = cccObj->GetCodepointSet(cccObj->GetEnumerationValue(mark));
+    const UnicodeSet & cc0Set = cccObj->GetCodepointSet(CCC_ns::NR); // ccc = 0, NotReorderable.
+    const UnicodeSet insertBeforeBlocked = cccSet + cc0Set;
+    std::vector<std::u32string> reorderings;
+    for (auto & prefix : prefixes) {
+        reorderings.push_back(prefix + (char32_t) mark);
+        int insert_pos = prefix.size() - 1;
+        while ((insert_pos >= 0) && (!insertBeforeBlocked.contains(prefix[insert_pos]))) {
+            reorderings.push_back(prefix.substr(0, insert_pos) + (char32_t) mark + prefix.substr(insert_pos));
+            insert_pos--;
+        }
+    }
+    return reorderings;
+}
+
+RE * allClusterOrderings(std::u32string cluster) {
+    std::vector<std::u32string> orderings = {cluster.substr(0,1)};
+    for (unsigned i = 1; i < cluster.size(); i++) {
+        orderings = allReorderedInsertions(orderings, cluster[i]);
+    }
+    std::vector<RE *> alts;
+    for (auto a : orderings) {
+        alts.push_back(u32string2re(a));
+    }
+    return makeAlt(alts.begin(), alts.end());
+}
+
+RE * allOrderings_RE(RE * re) {
+    if (Alt * alt = dyn_cast<Alt>(re)) {
+        std::vector<RE *> list;
+        list.reserve(alt->size());
+        for (RE * a : *alt) {
+            list.push_back(allOrderings_RE(a));
+        }
+        return makeAlt(list.begin(), list.end());
+    } else if (CC * cc = dyn_cast<CC>(re)) {
+        return cc;
+    } else if (Seq * seq = dyn_cast<Seq>(re)) {
+        // find and process all string pieces
+        std::vector<RE *> list;
+        unsigned size = seq->size();
+        unsigned i = 0;
+        while (i < size) {
+            std::u32string cluster = getCluster(seq, i);
+            if (cluster.size() > 0) {
+                list.push_back(allClusterOrderings(cluster));
+                i += cluster.size();
+            } else {
+                list.push_back(allOrderings_RE((*seq)[i]));
+                i++;
+            }
+        }
+        return makeSeq(list.begin(), list.end());
+    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
+        return makeAssertion(allOrderings_RE(a->getAsserted()), a->getKind(), a->getSense());
+    } else if (Rep * rep = dyn_cast<Rep>(re)) {
+        RE * expr = allOrderings_RE(rep->getRE());
+        return makeRep(expr, rep->getLB(), rep->getUB());
+    } else if (Diff * diff = dyn_cast<Diff>(re)) {
+        return makeDiff(allOrderings_RE(diff->getLH()), allOrderings_RE(diff->getRH()));
+    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
+        return makeIntersect(allOrderings_RE(e->getLH()), allOrderings_RE(e->getRH()));
+    } else if (Range * rg = dyn_cast<Range>(re)) {
+        return makeRange(allOrderings_RE(rg->getLo()), allOrderings_RE(rg->getHi()));
+    } else if (Group * g = dyn_cast<Group>(re)) {
+        return makeGroup(g->getMode(), allOrderings_RE(g->getRE()), g->getSense());
+    }
+    return re;
+}
+

icGREP/icgrep-devel/icgrep/re/Unicode/decomposition.h

@@ -16 +16 @@
     string (expanding decomposition).   In general, the result is
     a set of alternatives consisting of sequences for each expanding
-    decomposition as well as a single character class for all the
-    singledton decompositions as well as the codepoints that map to
+    decomposition plus a single character class for all the
+    singleton decompositions as well as the codepoints that map to
     themselves.
 */
@@ -36 +36 @@
 re::RE * Casefold_RE(re::RE * r);
 
+/* For every decomposed sequence in RE, add alternatives for all
+   canonically equivalent reorderings according to Unicode rules. */
+re::RE * allOrderings_RE(re::RE * re);
+
+
 #endif