Restoring authorship annotation for <bnagaev@yandex-team.ru>. Commit 1 of 2.

1 files changed, 382 insertions, 382 deletions

diff --git a/contrib/libs/hyperscan/src/nfagraph/ng_region.cpp b/contrib/libs/hyperscan/src/nfagraph/ng_region.cpp
index 2675be643f..a879e34695 100644
--- a/contrib/libs/hyperscan/src/nfagraph/ng_region.cpp
+++ b/contrib/libs/hyperscan/src/nfagraph/ng_region.cpp
@@ -1,476 +1,476 @@
-/*
+/* 
  * Copyright (c) 2015-2017, Intel Corporation
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- *  * Redistributions of source code must retain the above copyright notice,
- *    this list of conditions and the following disclaimer.
- *  * Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *  * Neither the name of Intel Corporation nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-/** \file
- * \brief Region analysis.
- *
- * Definition: a \a region is a subset of vertices in a graph such that:
- * - the edges entering the region are a cutset of the graph
- * - for every in-edge (u, v) to the region there exist edges (u, w) for all
- *       w in {w : w in region and w has an in-edge}
- * - the regions in a graph partition the graph
- *
- * Note:
- * - we partition a graph into the maximal number of regions
- * - similar properties for exit edges should hold as a consequence
- * - graph == sequence of regions
- * - a region is considered to have an epsilon vertex to allow jumps
- * - vertices which only lead to back edges need to be floated up in the topo
- *   order
- *
- * Algorithm overview:
- * -# topo-order over the DAG skeleton;
- * -# incrementally add vertices to the current region until the boundary edges
- *    form a valid cut-set;
- * -# for each back-edge, if the source and target are in different regions,
- *    merge the regions (and all intervening regions) into a common region.
- */
-#include "ng_region.h"
-
-#include "ng_holder.h"
-#include "ng_util.h"
-#include "ue2common.h"
-#include "util/container.h"
+ * 
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions are met: 
+ * 
+ *  * Redistributions of source code must retain the above copyright notice, 
+ *    this list of conditions and the following disclaimer. 
+ *  * Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in the 
+ *    documentation and/or other materials provided with the distribution. 
+ *  * Neither the name of Intel Corporation nor the names of its contributors 
+ *    may be used to endorse or promote products derived from this software 
+ *    without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
+ * POSSIBILITY OF SUCH DAMAGE. 
+ */ 
+ 
+/** \file 
+ * \brief Region analysis. 
+ * 
+ * Definition: a \a region is a subset of vertices in a graph such that: 
+ * - the edges entering the region are a cutset of the graph 
+ * - for every in-edge (u, v) to the region there exist edges (u, w) for all 
+ *       w in {w : w in region and w has an in-edge} 
+ * - the regions in a graph partition the graph 
+ * 
+ * Note: 
+ * - we partition a graph into the maximal number of regions 
+ * - similar properties for exit edges should hold as a consequence 
+ * - graph == sequence of regions 
+ * - a region is considered to have an epsilon vertex to allow jumps 
+ * - vertices which only lead to back edges need to be floated up in the topo 
+ *   order 
+ * 
+ * Algorithm overview: 
+ * -# topo-order over the DAG skeleton; 
+ * -# incrementally add vertices to the current region until the boundary edges 
+ *    form a valid cut-set; 
+ * -# for each back-edge, if the source and target are in different regions, 
+ *    merge the regions (and all intervening regions) into a common region. 
+ */ 
+#include "ng_region.h" 
+ 
+#include "ng_holder.h" 
+#include "ng_util.h" 
+#include "ue2common.h" 
+#include "util/container.h" 
 #include "util/flat_containers.h"
-#include "util/graph_range.h"
+#include "util/graph_range.h" 
 #include "util/graph_small_color_map.h"
-
-#include <set>
-#include <utility>
-#include <vector>
-
-#include <boost/graph/filtered_graph.hpp>
-#include <boost/graph/topological_sort.hpp>
-
-using namespace std;
-
-namespace ue2 {
-
+ 
+#include <set> 
+#include <utility> 
+#include <vector> 
+ 
+#include <boost/graph/filtered_graph.hpp> 
+#include <boost/graph/topological_sort.hpp> 
+ 
+using namespace std; 
+ 
+namespace ue2 { 
+ 
 using BackEdgeSet = unordered_set<NFAEdge>;
 using AcyclicGraph =
     boost::filtered_graph<NGHolder, bad_edge_filter<BackEdgeSet>>;
-
-namespace {
-struct exit_info {
-    explicit exit_info(NFAVertex v) : exit(v) {}
-
-    NFAVertex exit;
+ 
+namespace { 
+struct exit_info { 
+    explicit exit_info(NFAVertex v) : exit(v) {} 
+ 
+    NFAVertex exit; 
     flat_set<NFAVertex> open;
-};
-}
-
-static
-void checkAndAddExitCandidate(const AcyclicGraph &g,
+}; 
+} 
+ 
+static 
+void checkAndAddExitCandidate(const AcyclicGraph &g, 
                               const unordered_set<NFAVertex> &r, NFAVertex v,
                               vector<exit_info> &exits) {
     exit_info v_exit(v);
     auto &open = v_exit.open;
-
-    /* find the set of vertices reachable from v which are not in r */
-    for (auto w : adjacent_vertices_range(v, g)) {
-        if (!contains(r, w)) {
+ 
+    /* find the set of vertices reachable from v which are not in r */ 
+    for (auto w : adjacent_vertices_range(v, g)) { 
+        if (!contains(r, w)) { 
             open.insert(w);
-        }
-    }
-
+        } 
+    } 
+ 
     if (!open.empty()) {
         DEBUG_PRINTF("exit %zu\n", g[v].index);
         exits.push_back(move(v_exit));
-    }
-}
-
-static
+    } 
+} 
+ 
+static 
 void findExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r,
                vector<exit_info> &exits) {
     exits.clear();
-    for (auto v : r) {
-        checkAndAddExitCandidate(g, r, v, exits);
-    }
-}
-
-static
+    for (auto v : r) { 
+        checkAndAddExitCandidate(g, r, v, exits); 
+    } 
+} 
+ 
+static 
 void refineExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r,
                  NFAVertex new_v, vector<exit_info> &exits) {
     /* new_v is no long an open edge */
     for (auto &exit : exits) {
         exit.open.erase(new_v);
-    }
-
+    } 
+ 
     /* no open edges: no longer an exit */
     exits.erase(remove_if(exits.begin(), exits.end(),
                   [&](const exit_info &exit) { return exit.open.empty(); }),
                 exits.end());
 
-    checkAndAddExitCandidate(g, r, new_v, exits);
-}
-
-/** the set of exits from a candidate region are valid if: FIXME: document
- */
-static
-bool exitValid(UNUSED const AcyclicGraph &g, const vector<exit_info> &exits,
+    checkAndAddExitCandidate(g, r, new_v, exits); 
+} 
+ 
+/** the set of exits from a candidate region are valid if: FIXME: document 
+ */ 
+static 
+bool exitValid(UNUSED const AcyclicGraph &g, const vector<exit_info> &exits, 
                const flat_set<NFAVertex> &open_jumps) {
-    if (exits.empty() || (exits.size() < 2 && open_jumps.empty())) {
-        return true;
-    }
-    if (exits.size() == 1 && open_jumps.size() == 1) {
+    if (exits.empty() || (exits.size() < 2 && open_jumps.empty())) { 
+        return true; 
+    } 
+    if (exits.size() == 1 && open_jumps.size() == 1) { 
         DEBUG_PRINTF("oj %zu, e %zu\n", g[*open_jumps.begin()].index,
-                     g[exits[0].exit].index);
-        if (*open_jumps.begin() == exits[0].exit) {
-            return true;
-        }
-    }
-
-    assert(!exits.empty());
-    const auto &enters = exits.front().open;
-
-    if (!open_jumps.empty() && enters != open_jumps) {
-        return false;
-    }
-
-    for (auto it = begin(exits) + 1; it != end(exits); ++it) {
-        if (it->open != enters) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
-static
+                     g[exits[0].exit].index); 
+        if (*open_jumps.begin() == exits[0].exit) { 
+            return true; 
+        } 
+    } 
+ 
+    assert(!exits.empty()); 
+    const auto &enters = exits.front().open; 
+ 
+    if (!open_jumps.empty() && enters != open_jumps) { 
+        return false; 
+    } 
+ 
+    for (auto it = begin(exits) + 1; it != end(exits); ++it) { 
+        if (it->open != enters) { 
+            return false; 
+        } 
+    } 
+ 
+    return true; 
+} 
+ 
+static 
 void setRegion(const unordered_set<NFAVertex> &r, u32 rid,
                unordered_map<NFAVertex, u32> &regions) {
-    for (auto v : r) {
-        regions[v] = rid;
-    }
-}
-
-static
-void buildInitialCandidate(const AcyclicGraph &g,
-                           vector<NFAVertex>::const_reverse_iterator &it,
-                           const vector<NFAVertex>::const_reverse_iterator &ite,
+    for (auto v : r) { 
+        regions[v] = rid; 
+    } 
+} 
+ 
+static 
+void buildInitialCandidate(const AcyclicGraph &g, 
+                           vector<NFAVertex>::const_reverse_iterator &it, 
+                           const vector<NFAVertex>::const_reverse_iterator &ite, 
                            unordered_set<NFAVertex> &candidate,
-                           /* in exits of prev region;
-                            * out exits from candidate */
+                           /* in exits of prev region; 
+                            * out exits from candidate */ 
                            vector<exit_info> &exits,
                            flat_set<NFAVertex> &open_jumps) {
-    if (it == ite) {
+    if (it == ite) { 
         candidate.clear();
         exits.clear();
-        return;
-    }
-
+        return; 
+    } 
+ 
     if (exits.empty()) {
-        DEBUG_PRINTF("odd\n");
+        DEBUG_PRINTF("odd\n"); 
         candidate.clear();
         DEBUG_PRINTF("adding %zu to initial\n", g[*it].index);
         candidate.insert(*it);
         open_jumps.erase(*it);
         checkAndAddExitCandidate(g, candidate, *it, exits);
-        ++it;
-        return;
-    }
-
+        ++it; 
+        return; 
+    } 
+ 
     // Note: findExits() will clear exits, so it's safe to mutate/move its
     // elements here.
     auto &enters = exits.front().open;
     candidate.clear();
-
-    for (; it != ite; ++it) {
+ 
+    for (; it != ite; ++it) { 
         DEBUG_PRINTF("adding %zu to initial\n", g[*it].index);
         candidate.insert(*it);
-        if (contains(enters, *it)) {
-            break;
-        }
-    }
-
-    if (it != ite) {
-        enters.erase(*it);
+        if (contains(enters, *it)) { 
+            break; 
+        } 
+    } 
+ 
+    if (it != ite) { 
+        enters.erase(*it); 
         open_jumps = move(enters);
         DEBUG_PRINTF("oj size = %zu\n", open_jumps.size());
-        ++it;
-    } else {
+        ++it; 
+    } else { 
         open_jumps.clear();
-    }
-
+    } 
+ 
     findExits(g, candidate, exits);
-}
-
-static
-void findDagLeaders(const NGHolder &h, const AcyclicGraph &g,
-                    const vector<NFAVertex> &topo,
+} 
+ 
+static 
+void findDagLeaders(const NGHolder &h, const AcyclicGraph &g, 
+                    const vector<NFAVertex> &topo, 
                     unordered_map<NFAVertex, u32> &regions) {
-    assert(!topo.empty());
-    u32 curr_id = 0;
+    assert(!topo.empty()); 
+    u32 curr_id = 0; 
     auto t_it = topo.rbegin();
     unordered_set<NFAVertex> candidate;
     flat_set<NFAVertex> open_jumps;
     DEBUG_PRINTF("adding %zu to current\n", g[*t_it].index);
-    assert(t_it != topo.rend());
-    candidate.insert(*t_it++);
+    assert(t_it != topo.rend()); 
+    candidate.insert(*t_it++); 
     DEBUG_PRINTF("adding %zu to current\n", g[*t_it].index);
-    assert(t_it != topo.rend());
-    candidate.insert(*t_it++);
-
+    assert(t_it != topo.rend()); 
+    candidate.insert(*t_it++); 
+ 
     vector<exit_info> exits;
     findExits(g, candidate, exits);
 
-    while (t_it != topo.rend()) {
-        assert(!candidate.empty());
-
-        if (exitValid(g, exits, open_jumps)) {
-            if (contains(candidate, h.accept) && !open_jumps.empty()) {
-                /* we have tried to make an optional region containing accept as
-                 * we have an open jump to eod. This candidate region needs to
-                 * be put in with the previous region. */
-                curr_id--;
-                DEBUG_PRINTF("merging in with region %u\n", curr_id);
-            } else {
-                DEBUG_PRINTF("setting region %u\n", curr_id);
-            }
-            setRegion(candidate, curr_id++, regions);
+    while (t_it != topo.rend()) { 
+        assert(!candidate.empty()); 
+ 
+        if (exitValid(g, exits, open_jumps)) { 
+            if (contains(candidate, h.accept) && !open_jumps.empty()) { 
+                /* we have tried to make an optional region containing accept as 
+                 * we have an open jump to eod. This candidate region needs to 
+                 * be put in with the previous region. */ 
+                curr_id--; 
+                DEBUG_PRINTF("merging in with region %u\n", curr_id); 
+            } else { 
+                DEBUG_PRINTF("setting region %u\n", curr_id); 
+            } 
+            setRegion(candidate, curr_id++, regions); 
             buildInitialCandidate(g, t_it, topo.rend(), candidate, exits,
                                   open_jumps);
-        } else {
-            NFAVertex curr = *t_it;
+        } else { 
+            NFAVertex curr = *t_it; 
             DEBUG_PRINTF("adding %zu to current\n", g[curr].index);
-            candidate.insert(curr);
-            open_jumps.erase(curr);
+            candidate.insert(curr); 
+            open_jumps.erase(curr); 
             refineExits(g, candidate, *t_it, exits);
-            DEBUG_PRINTF("    open jumps %zu exits %zu\n", open_jumps.size(),
-                         exits.size());
-            ++t_it;
-        }
-    }
-    /* assert exits valid */
-    setRegion(candidate, curr_id, regions);
-}
-
-static
-void mergeUnderBackEdges(const NGHolder &g, const vector<NFAVertex> &topo,
-                         const BackEdgeSet &backEdges,
+            DEBUG_PRINTF("    open jumps %zu exits %zu\n", open_jumps.size(), 
+                         exits.size()); 
+            ++t_it; 
+        } 
+    } 
+    /* assert exits valid */ 
+    setRegion(candidate, curr_id, regions); 
+} 
+ 
+static 
+void mergeUnderBackEdges(const NGHolder &g, const vector<NFAVertex> &topo, 
+                         const BackEdgeSet &backEdges, 
                          unordered_map<NFAVertex, u32> &regions) {
-    for (const auto &e : backEdges) {
-        NFAVertex u = source(e, g);
-        NFAVertex v = target(e, g);
-
-        u32 ru = regions[u];
-        u32 rv = regions[v];
-        if (ru == rv) {
-            continue;
-        }
-
+    for (const auto &e : backEdges) { 
+        NFAVertex u = source(e, g); 
+        NFAVertex v = target(e, g); 
+ 
+        u32 ru = regions[u]; 
+        u32 rv = regions[v]; 
+        if (ru == rv) { 
+            continue; 
+        } 
+ 
         DEBUG_PRINTF("merging v = %zu(%u), u = %zu(%u)\n", g[v].index, rv,
-                     g[u].index, ru);
-        assert(rv < ru);
-
-        for (auto t : topo) {
-            u32 r = regions[t];
-            if (r <= ru && r > rv) {
-                regions[t] = rv;
-            } else if (r > ru) {
-                regions[t] = rv + r - ru;
-            }
-        }
-    }
-}
-
-static
-void reorderSpecials(const NGHolder &w, const AcyclicGraph &acyclic_g,
-                     vector<NFAVertex> &topoOrder) {
-    // Start is last element of reverse topo ordering.
-    auto it = find(topoOrder.begin(), topoOrder.end(), w.start);
-    if (it != topoOrder.end() - 1) {
-        DEBUG_PRINTF("repositioning start\n");
-        assert(it != topoOrder.end());
-        topoOrder.erase(it);
-        topoOrder.insert(topoOrder.end(), w.start);
-    }
-
-    // StartDs is second-to-last element of reverse topo ordering.
-    it = find(topoOrder.begin(), topoOrder.end(), w.startDs);
-    if (it != topoOrder.end() - 2) {
-        DEBUG_PRINTF("repositioning start ds\n");
-        assert(it != topoOrder.end());
-        topoOrder.erase(it);
-        topoOrder.insert(topoOrder.end() - 1, w.startDs);
-    }
-
-    // AcceptEOD is first element of reverse topo ordering.
-    it = find(topoOrder.begin(), topoOrder.end(), w.acceptEod);
-    if (it != topoOrder.begin()) {
-        DEBUG_PRINTF("repositioning accept\n");
-        assert(it != topoOrder.end());
-        topoOrder.erase(it);
-        topoOrder.insert(topoOrder.begin(), w.acceptEod);
-    }
-
-    // Accept is second element of reverse topo ordering, if it's connected.
-    it = find(topoOrder.begin(), topoOrder.end(), w.accept);
-    if (it != topoOrder.begin() + 1) {
-        DEBUG_PRINTF("repositioning accept\n");
-        assert(it != topoOrder.end());
-        topoOrder.erase(it);
-        if (in_degree(w.accept, acyclic_g) != 0) {
-            topoOrder.insert(topoOrder.begin() + 1, w.accept);
-        }
-    }
-}
-
-static
-void liftSinks(const AcyclicGraph &acyclic_g, vector<NFAVertex> &topoOrder) {
+                     g[u].index, ru); 
+        assert(rv < ru); 
+ 
+        for (auto t : topo) { 
+            u32 r = regions[t]; 
+            if (r <= ru && r > rv) { 
+                regions[t] = rv; 
+            } else if (r > ru) { 
+                regions[t] = rv + r - ru; 
+            } 
+        } 
+    } 
+} 
+ 
+static 
+void reorderSpecials(const NGHolder &w, const AcyclicGraph &acyclic_g, 
+                     vector<NFAVertex> &topoOrder) { 
+    // Start is last element of reverse topo ordering. 
+    auto it = find(topoOrder.begin(), topoOrder.end(), w.start); 
+    if (it != topoOrder.end() - 1) { 
+        DEBUG_PRINTF("repositioning start\n"); 
+        assert(it != topoOrder.end()); 
+        topoOrder.erase(it); 
+        topoOrder.insert(topoOrder.end(), w.start); 
+    } 
+ 
+    // StartDs is second-to-last element of reverse topo ordering. 
+    it = find(topoOrder.begin(), topoOrder.end(), w.startDs); 
+    if (it != topoOrder.end() - 2) { 
+        DEBUG_PRINTF("repositioning start ds\n"); 
+        assert(it != topoOrder.end()); 
+        topoOrder.erase(it); 
+        topoOrder.insert(topoOrder.end() - 1, w.startDs); 
+    } 
+ 
+    // AcceptEOD is first element of reverse topo ordering. 
+    it = find(topoOrder.begin(), topoOrder.end(), w.acceptEod); 
+    if (it != topoOrder.begin()) { 
+        DEBUG_PRINTF("repositioning accept\n"); 
+        assert(it != topoOrder.end()); 
+        topoOrder.erase(it); 
+        topoOrder.insert(topoOrder.begin(), w.acceptEod); 
+    } 
+ 
+    // Accept is second element of reverse topo ordering, if it's connected. 
+    it = find(topoOrder.begin(), topoOrder.end(), w.accept); 
+    if (it != topoOrder.begin() + 1) { 
+        DEBUG_PRINTF("repositioning accept\n"); 
+        assert(it != topoOrder.end()); 
+        topoOrder.erase(it); 
+        if (in_degree(w.accept, acyclic_g) != 0) { 
+            topoOrder.insert(topoOrder.begin() + 1, w.accept); 
+        } 
+    } 
+} 
+ 
+static 
+void liftSinks(const AcyclicGraph &acyclic_g, vector<NFAVertex> &topoOrder) { 
     unordered_set<NFAVertex> sinks;
-    for (auto v : vertices_range(acyclic_g)) {
-        if (is_special(v, acyclic_g)) {
-            continue;
-        }
-
-        if (isLeafNode(v, acyclic_g)) {
+    for (auto v : vertices_range(acyclic_g)) { 
+        if (is_special(v, acyclic_g)) { 
+            continue; 
+        } 
+ 
+        if (isLeafNode(v, acyclic_g)) { 
             DEBUG_PRINTF("sink found %zu\n", acyclic_g[v].index);
             sinks.insert(NFAVertex(v));
-        }
-    }
-
-    if (sinks.empty()) {
-        DEBUG_PRINTF("no sinks found\n");
-        return;
-    }
-
-    bool changed;
-    do {
-        DEBUG_PRINTF("look\n");
-        changed = false;
-        for (auto v : vertices_range(acyclic_g)) {
+        } 
+    } 
+ 
+    if (sinks.empty()) { 
+        DEBUG_PRINTF("no sinks found\n"); 
+        return; 
+    } 
+ 
+    bool changed; 
+    do { 
+        DEBUG_PRINTF("look\n"); 
+        changed = false; 
+        for (auto v : vertices_range(acyclic_g)) { 
             if (is_special(v, acyclic_g) || contains(sinks, NFAVertex(v))) {
-                continue;
-            }
-
-            for (auto w : adjacent_vertices_range(v, acyclic_g)) {
+                continue; 
+            } 
+ 
+            for (auto w : adjacent_vertices_range(v, acyclic_g)) { 
                 if (!contains(sinks, NFAVertex(w))) {
-                    goto next;
-                }
-            }
-
+                    goto next; 
+                } 
+            } 
+ 
             DEBUG_PRINTF("sink found %zu\n", acyclic_g[v].index);
             sinks.insert(NFAVertex(v));
-            changed = true;
-        next:;
-        }
-    } while (changed);
-
-    for (auto ri = topoOrder.rbegin() + 1; ri != topoOrder.rend(); ++ri) {
-        if (!contains(sinks, *ri)) {
-            continue;
-        }
-        NFAVertex s = *ri;
+            changed = true; 
+        next:; 
+        } 
+    } while (changed); 
+ 
+    for (auto ri = topoOrder.rbegin() + 1; ri != topoOrder.rend(); ++ri) { 
+        if (!contains(sinks, *ri)) { 
+            continue; 
+        } 
+        NFAVertex s = *ri; 
         DEBUG_PRINTF("handling sink %zu\n", acyclic_g[s].index);
         unordered_set<NFAVertex> parents;
-        for (const auto &e : in_edges_range(s, acyclic_g)) {
+        for (const auto &e : in_edges_range(s, acyclic_g)) { 
             parents.insert(NFAVertex(source(e, acyclic_g)));
-        }
-
-        /* vertex has no children not reachable on a back edge, bubble the
-         * vertex up the topo order to be near its parents */
-        vector<NFAVertex>::reverse_iterator rj = ri;
-        --rj;
-        while (rj != topoOrder.rbegin() && !contains(parents, *rj)) {
-            /* sink is in rj + 1 */
-            assert(*(rj + 1) == s);
-            DEBUG_PRINTF("lifting\n");
-            using std::swap;
-            swap(*rj, *(rj + 1));
-            --rj;
-        }
-    }
-}
-
+        } 
+ 
+        /* vertex has no children not reachable on a back edge, bubble the 
+         * vertex up the topo order to be near its parents */ 
+        vector<NFAVertex>::reverse_iterator rj = ri; 
+        --rj; 
+        while (rj != topoOrder.rbegin() && !contains(parents, *rj)) { 
+            /* sink is in rj + 1 */ 
+            assert(*(rj + 1) == s); 
+            DEBUG_PRINTF("lifting\n"); 
+            using std::swap; 
+            swap(*rj, *(rj + 1)); 
+            --rj; 
+        } 
+    } 
+} 
+ 
 using ColorMap = decltype(make_small_color_map(NGHolder()));
 
-/** Build a reverse topo ordering (with only the specials that are in use). We
- * also want to ensure vertices which only lead to back edges are placed near
- * their parents. */
-static
-vector<NFAVertex> buildTopoOrder(const NGHolder &w,
-                                 const AcyclicGraph &acyclic_g,
+/** Build a reverse topo ordering (with only the specials that are in use). We 
+ * also want to ensure vertices which only lead to back edges are placed near 
+ * their parents. */ 
+static 
+vector<NFAVertex> buildTopoOrder(const NGHolder &w, 
+                                 const AcyclicGraph &acyclic_g, 
                                  ColorMap &colours) {
-    vector<NFAVertex> topoOrder;
+    vector<NFAVertex> topoOrder; 
     topoOrder.reserve(num_vertices(w));
-
+ 
     topological_sort(acyclic_g, back_inserter(topoOrder),
                      color_map(colours));
-
-    reorderSpecials(w, acyclic_g, topoOrder);
-
-    if (topoOrder.empty()) {
-        return topoOrder;
-    }
-
-    liftSinks(acyclic_g, topoOrder);
-
-    DEBUG_PRINTF("TOPO ORDER\n");
-    for (auto ri = topoOrder.rbegin(); ri != topoOrder.rend(); ++ri) {
+ 
+    reorderSpecials(w, acyclic_g, topoOrder); 
+ 
+    if (topoOrder.empty()) { 
+        return topoOrder; 
+    } 
+ 
+    liftSinks(acyclic_g, topoOrder); 
+ 
+    DEBUG_PRINTF("TOPO ORDER\n"); 
+    for (auto ri = topoOrder.rbegin(); ri != topoOrder.rend(); ++ri) { 
         DEBUG_PRINTF("[%zu]\n", acyclic_g[*ri].index);
-    }
-    DEBUG_PRINTF("----------\n");
-
-    return topoOrder;
-}
-
+    } 
+    DEBUG_PRINTF("----------\n"); 
+ 
+    return topoOrder; 
+} 
+ 
 unordered_map<NFAVertex, u32> assignRegions(const NGHolder &g) {
-    assert(hasCorrectlyNumberedVertices(g));
-    const u32 numVertices = num_vertices(g);
-    DEBUG_PRINTF("assigning regions for %u vertices in holder\n", numVertices);
-
+    assert(hasCorrectlyNumberedVertices(g)); 
+    const u32 numVertices = num_vertices(g); 
+    DEBUG_PRINTF("assigning regions for %u vertices in holder\n", numVertices); 
+ 
     auto colours = make_small_color_map(g);
-
-    // Build an acyclic graph for this NGHolder.
-    BackEdgeSet deadEdges;
+ 
+    // Build an acyclic graph for this NGHolder. 
+    BackEdgeSet deadEdges; 
     depth_first_search(g,
                        visitor(BackEdges<BackEdgeSet>(deadEdges))
                        .root_vertex(g.start)
                        .color_map(colours));
-
+ 
     auto af = make_bad_edge_filter(&deadEdges);
     AcyclicGraph acyclic_g(g, af);
-
-    // Build a (reverse) topological ordering.
-    vector<NFAVertex> topoOrder = buildTopoOrder(g, acyclic_g, colours);
-
-    // Everybody starts in region 0.
+ 
+    // Build a (reverse) topological ordering. 
+    vector<NFAVertex> topoOrder = buildTopoOrder(g, acyclic_g, colours); 
+ 
+    // Everybody starts in region 0. 
     unordered_map<NFAVertex, u32> regions;
-    regions.reserve(numVertices);
-    for (auto v : vertices_range(g)) {
-        regions.emplace(v, 0);
-    }
-
-    findDagLeaders(g, acyclic_g, topoOrder, regions);
-    mergeUnderBackEdges(g, topoOrder, deadEdges, regions);
-
-    return regions;
-}
-
-} // namespace ue2
+    regions.reserve(numVertices); 
+    for (auto v : vertices_range(g)) { 
+        regions.emplace(v, 0); 
+    } 
+ 
+    findDagLeaders(g, acyclic_g, topoOrder, regions); 
+    mergeUnderBackEdges(g, topoOrder, deadEdges, regions); 
+ 
+    return regions; 
+} 
+ 
+} // namespace ue2