kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

highlighters.cc (97065B)


      1 #include "highlighters.hh"
      2 
      3 #include "assert.hh"
      4 #include "buffer_utils.hh"
      5 #include "debug.hh"
      6 #include "changes.hh"
      7 #include "command_manager.hh"
      8 #include "context.hh"
      9 #include "display_buffer.hh"
     10 #include "face_registry.hh"
     11 #include "highlighter_group.hh"
     12 #include "line_modification.hh"
     13 #include "option_manager.hh"
     14 #include "option_types.hh"
     15 #include "parameters_parser.hh"
     16 #include "ranges.hh"
     17 #include "regex.hh"
     18 #include "register_manager.hh"
     19 #include "string.hh"
     20 #include "utf8.hh"
     21 #include "utf8_iterator.hh"
     22 #include "window.hh"
     23 #include "unicode.hh"
     24 
     25 #include <cstdio>
     26 #include <limits>
     27 
     28 namespace Kakoune
     29 {
     30 
     31 template<typename Func>
     32 UniquePtr<Highlighter> make_highlighter(Func func, HighlightPass pass = HighlightPass::Colorize)
     33 {
     34     struct SimpleHighlighter : public Highlighter
     35     {
     36         SimpleHighlighter(Func func, HighlightPass pass)
     37           : Highlighter{pass}, m_func{std::move(func)} {}
     38 
     39     private:
     40         void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
     41         {
     42             m_func(context, display_buffer, range);
     43         }
     44         Func m_func;
     45     };
     46     return make_unique_ptr<SimpleHighlighter>(std::move(func), pass);
     47 }
     48 
     49 template<typename T>
     50 void highlight_range(DisplayBuffer& display_buffer,
     51                      BufferCoord begin, BufferCoord end,
     52                      bool skip_replaced, T func)
     53 {
     54     // tolerate begin > end as that can be triggered by wrong encodings
     55     if (begin >= end or end <= display_buffer.range().begin
     56                      or begin >= display_buffer.range().end)
     57         return;
     58 
     59     for (auto& line : display_buffer.lines())
     60     {
     61         auto& range = line.range();
     62         if (range.end <= begin or end < range.begin)
     63             continue;
     64 
     65         for (auto atom_it = line.begin(); atom_it != line.end(); ++atom_it)
     66         {
     67             bool is_replaced = atom_it->type() == DisplayAtom::ReplacedRange;
     68 
     69             if (not atom_it->has_buffer_range() or
     70                 (skip_replaced and is_replaced) or
     71                 end <= atom_it->begin() or begin >= atom_it->end())
     72                 continue;
     73 
     74             if (not is_replaced and begin > atom_it->begin())
     75                 atom_it = ++line.split(atom_it, begin);
     76 
     77             if (not is_replaced and end < atom_it->end())
     78             {
     79                 atom_it = line.split(atom_it, end);
     80                 func(*atom_it);
     81                 ++atom_it;
     82             }
     83             else
     84                 func(*atom_it);
     85         }
     86     }
     87 }
     88 
     89 template<typename T>
     90 void replace_range(DisplayBuffer& display_buffer,
     91                    BufferCoord begin, BufferCoord end, T func)
     92 {
     93     // tolerate begin > end as that can be triggered by wrong encodings
     94     if (begin > end or end < display_buffer.range().begin or begin > display_buffer.range().end)
     95         return;
     96 
     97     auto& lines = display_buffer.lines();
     98     auto first_it = std::lower_bound(lines.begin(), lines.end(), begin, [](const DisplayLine& l, const BufferCoord& c) { return l.range().end < c; });
     99     if (first_it == lines.end())
    100         return;
    101 
    102     auto first_atom_it = std::find_if(first_it->begin(), first_it->end(), [&begin](const DisplayAtom& a) { return a.has_buffer_range() and a.end() > begin; });
    103     first_atom_it = first_it->split(begin);
    104 
    105     auto last_it = std::lower_bound(first_it, lines.end(), end, [](const DisplayLine& l, const BufferCoord& c) { return l.range().end < c; });
    106 
    107     if (first_it == last_it)
    108     {
    109         auto first_atom_idx = first_atom_it - first_it->begin();
    110         auto end_atom_it = first_it->split(end);
    111         first_atom_it = first_it->erase(first_it->begin() + first_atom_idx, end_atom_it);
    112     }
    113     else
    114     {
    115         first_atom_it = first_it->erase(first_atom_it, first_it->end());
    116         if (last_it != lines.end())
    117         {
    118             auto end_atom_it = last_it->split(end);
    119             end_atom_it = last_it->erase(last_it->begin(), end_atom_it);
    120 
    121             first_atom_it = first_it->insert(first_atom_it, end_atom_it, last_it->end());
    122             ++last_it;
    123         }
    124         first_it = --lines.erase(first_it+1, last_it);
    125     }
    126 
    127     func(lines, first_it, first_atom_it);
    128 }
    129 
    130 auto apply_face = [](const Face& face)
    131 {
    132     return [&face](DisplayAtom& atom) {
    133         atom.face = merge_faces(atom.face, face);
    134     };
    135 };
    136 
    137 const HighlighterDesc fill_desc = {
    138     "Fill the whole highlighted range with the given face",
    139     {}
    140 };
    141 static UniquePtr<Highlighter> create_fill_highlighter(HighlighterParameters params, Highlighter*)
    142 {
    143     if (params.size() != 1)
    144         throw runtime_error("wrong parameter count");
    145 
    146     return make_highlighter(
    147         [spec=parse_face(params[0])](HighlightContext context, DisplayBuffer& display_buffer,
    148                                      BufferRange range) {
    149             highlight_range(display_buffer, range.begin, range.end, false,
    150                             apply_face(context.context.faces()[spec]));
    151         });
    152 }
    153 
    154 template<typename T>
    155 struct BufferSideCache
    156 {
    157     BufferSideCache() : m_id{get_free_value_id()} {}
    158 
    159     T& get(const Buffer& buffer)
    160     {
    161         Value& cache_val = buffer.values()[m_id];
    162         if (not cache_val)
    163             cache_val = Value(T{});
    164         return cache_val.as<T>();
    165     }
    166 private:
    167     ValueId m_id;
    168 };
    169 
    170 using FacesSpec = Vector<std::pair<size_t, FaceSpec>, MemoryDomain::Highlight>;
    171 
    172 const HighlighterDesc regex_desc = {
    173     "Parameters: <regex> <capture num>:<face> <capture num>:<face>...\n"
    174     "Highlights the matches for captures from the regex with the given faces",
    175     {}
    176 };
    177 class RegexHighlighter : public Highlighter
    178 {
    179 public:
    180     RegexHighlighter(Regex regex, FacesSpec faces)
    181         : Highlighter{HighlightPass::Colorize},
    182           m_regex{std::move(regex)},
    183           m_faces{std::move(faces)}
    184     {
    185         ensure_first_face_is_capture_0();
    186     }
    187 
    188     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
    189     {
    190         auto overlaps = [](const BufferRange& lhs, const BufferRange& rhs) {
    191             return lhs.begin < rhs.begin ? lhs.end > rhs.begin
    192                                          : rhs.end > lhs.begin;
    193         };
    194 
    195         if (not overlaps(display_buffer.range(), range))
    196             return;
    197 
    198         const auto faces = m_faces | transform([&faces = context.context.faces()](auto&& spec) {
    199                 return faces[spec.second];
    200             }) | gather<Vector<Face>>();
    201 
    202         const auto& matches = get_matches(context.context.buffer(), display_buffer.range(), range);
    203         kak_assert(matches.size() % m_faces.size() == 0);
    204         for (size_t m = 0; m < matches.size(); ++m)
    205         {
    206             auto& face = faces[m % faces.size()];
    207             if (face == Face{})
    208                 continue;
    209 
    210             highlight_range(display_buffer,
    211                             matches[m].begin, matches[m].end,
    212                             false, apply_face(face));
    213         }
    214     }
    215 
    216     void reset(Regex regex, FacesSpec faces)
    217     {
    218         m_regex = std::move(regex);
    219         m_faces = std::move(faces);
    220         ensure_first_face_is_capture_0();
    221         ++m_regex_version;
    222     }
    223 
    224     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
    225     {
    226         if (params.size() < 2)
    227             throw runtime_error("wrong parameter count");
    228 
    229         Regex re{params[0], RegexCompileFlags::Optimize};
    230 
    231         FacesSpec faces;
    232         for (auto& spec : params.subrange(1))
    233         {
    234             auto colon = find(spec, ':');
    235             if (colon == spec.end())
    236                 throw runtime_error(format("wrong face spec: '{}' expected <capture>:<facespec>", spec));
    237             const StringView capture_name{spec.begin(), colon};
    238             const int capture = str_to_int_ifp(capture_name).value_or_compute([&] {
    239                 return re.named_capture_index(capture_name);
    240             });
    241             if (capture < 0)
    242                 throw runtime_error(format("capture name {} is neither a capture index, nor an existing capture name",
    243                                            capture_name));
    244             faces.emplace_back(capture, parse_face({colon+1, spec.end()}));
    245         }
    246 
    247         return make_unique_ptr<RegexHighlighter>(std::move(re), std::move(faces));
    248     }
    249 
    250 private:
    251     // stores the range for each highlighted capture of each match
    252     using MatchList = Vector<BufferRange, MemoryDomain::Highlight>;
    253     struct Cache
    254     {
    255         size_t m_timestamp = -1;
    256         size_t m_regex_version = -1;
    257         struct RangeAndMatches { BufferRange range; MatchList matches; };
    258         using RangeAndMatchesList = Vector<RangeAndMatches, MemoryDomain::Highlight>;
    259         HashMap<BufferRange, RangeAndMatchesList, MemoryDomain::Highlight> m_matches;
    260     };
    261     BufferSideCache<Cache> m_cache;
    262 
    263     Regex     m_regex;
    264     FacesSpec m_faces;
    265 
    266     size_t m_regex_version = 0;
    267 
    268     void ensure_first_face_is_capture_0()
    269     {
    270         if (m_faces.empty())
    271             return;
    272 
    273         std::sort(m_faces.begin(), m_faces.end(),
    274                   [](auto&& lhs, auto&& rhs) { return lhs.first < rhs.first; });
    275         if (m_faces[0].first != 0)
    276             m_faces.emplace(m_faces.begin(), 0, FaceSpec{});
    277     }
    278 
    279     void add_matches(const Buffer& buffer, MatchList& matches, BufferRange range)
    280     {
    281         kak_assert(matches.size() % m_faces.size() == 0);
    282         for (auto&& match : RegexIterator{get_iterator(buffer, range.begin),
    283                                           get_iterator(buffer, range.end),
    284                                           buffer.begin(), buffer.end(), m_regex,
    285                                           match_flags(is_bol(range.begin),
    286                                                       is_eol(buffer, range.end),
    287                                                       is_bow(buffer, range.begin),
    288                                                       is_eow(buffer, range.end))})
    289         {
    290             for (auto& face : m_faces)
    291             {
    292                 const auto& sub = match[face.first];
    293                 matches.push_back({sub.first.coord(), sub.second.coord()});
    294             }
    295         }
    296     }
    297 
    298     const MatchList& get_matches(const Buffer& buffer, BufferRange display_range, BufferRange buffer_range)
    299     {
    300         Cache& cache = m_cache.get(buffer);
    301 
    302         if (cache.m_regex_version != m_regex_version or
    303             cache.m_timestamp != buffer.timestamp() or
    304             accumulate(cache.m_matches, (size_t)0, [](size_t c, auto&& m) { return c + m.value.size(); }) > 1000)
    305         {
    306             cache.m_matches.clear();
    307             cache.m_timestamp = buffer.timestamp();
    308             cache.m_regex_version = m_regex_version;
    309         }
    310 
    311         auto& matches = cache.m_matches[buffer_range];
    312 
    313         const LineCount line_offset = 3;
    314         BufferRange range{std::max<BufferCoord>(buffer_range.begin, display_range.begin.line - line_offset),
    315                           std::min<BufferCoord>(buffer_range.end, display_range.end.line + line_offset)};
    316 
    317         auto it = std::upper_bound(matches.begin(), matches.end(), range.begin,
    318                                    [](const BufferCoord& lhs, const Cache::RangeAndMatches& rhs)
    319                                    { return lhs < rhs.range.end; });
    320 
    321         if (it == matches.end() or it->range.begin > range.end)
    322         {
    323             it = matches.insert(it, Cache::RangeAndMatches{range, {}});
    324             add_matches(buffer, it->matches, range);
    325         }
    326         else if (it->matches.empty())
    327         {
    328             it->range = range;
    329             add_matches(buffer, it->matches, range);
    330         }
    331         else
    332         {
    333             // Here we extend the matches, that is not strictly valid,
    334             // but may work nicely with every reasonable regex, and
    335             // greatly reduces regex parsing. To change if we encounter
    336             // regex that do not work great with that.
    337             BufferRange& old_range = it->range;
    338             MatchList& matches = it->matches;
    339 
    340             // Thanks to the ensure_first_face_is_capture_0 method, we know
    341             // these point to the first/last matches capture 0.
    342             auto first_end = matches.begin()->end;
    343             auto last_end = (matches.end() - m_faces.size())->end;
    344 
    345             // add regex matches from new begin to old first match end
    346             if (range.begin < old_range.begin)
    347             {
    348                 matches.erase(matches.begin(), matches.begin() + m_faces.size());
    349                 size_t pivot = matches.size();
    350                 old_range.begin = range.begin;
    351                 add_matches(buffer, matches, {range.begin, first_end});
    352 
    353                 std::rotate(matches.begin(), matches.begin() + pivot, matches.end());
    354             }
    355             // add regex matches from old last match begin to new end
    356             if (old_range.end < range.end)
    357             {
    358                 old_range.end = range.end;
    359                 add_matches(buffer, matches, {last_end, range.end});
    360             }
    361         }
    362         return it->matches;
    363     }
    364 };
    365 
    366 template<typename RegexGetter, typename FaceGetter>
    367 class DynamicRegexHighlighter : public Highlighter
    368 {
    369 public:
    370     DynamicRegexHighlighter(RegexGetter get_regex, FaceGetter resolve_faces)
    371       : Highlighter{HighlightPass::Colorize},
    372         m_get_regex(std::move(get_regex)),
    373         m_resolve_faces(std::move(resolve_faces)),
    374         m_highlighter(Regex{}, FacesSpec{}) {}
    375 
    376     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
    377     {
    378         Regex regex = m_get_regex(context.context);
    379         FacesSpec face = regex.empty() ? FacesSpec{} : m_resolve_faces(regex);
    380         if (regex != m_last_regex or face != m_last_face)
    381         {
    382             m_last_regex = std::move(regex);
    383             m_last_face = face;
    384             if (not m_last_regex.empty())
    385                 m_highlighter.reset(m_last_regex, m_last_face);
    386         }
    387         if (not m_last_regex.empty() and not m_last_face.empty())
    388             m_highlighter.highlight(context, display_buffer, range);
    389     }
    390 
    391 private:
    392     Regex       m_last_regex;
    393     RegexGetter m_get_regex;
    394 
    395     FacesSpec   m_last_face;
    396     FaceGetter  m_resolve_faces;
    397 
    398     RegexHighlighter m_highlighter;
    399 };
    400 
    401 const HighlighterDesc dynamic_regex_desc = {
    402     "Parameters: <expr> <capture num>:<face> <capture num>:<face>...\n"
    403     "Evaluate expression at every redraw to gather a regex",
    404     {}
    405 };
    406 UniquePtr<Highlighter> create_dynamic_regex_highlighter(HighlighterParameters params, Highlighter*)
    407 {
    408     if (params.size() < 2)
    409         throw runtime_error("wrong parameter count");
    410 
    411     Vector<std::pair<String, FaceSpec>> faces;
    412     for (auto& spec : params.subrange(1))
    413     {
    414         auto colon = find(spec, ':');
    415         if (colon == spec.end())
    416             throw runtime_error("wrong face spec: '" + spec +
    417                                  "' expected <capture>:<facespec>");
    418         faces.emplace_back(String{spec.begin(), colon}, parse_face({colon+1, spec.end()}));
    419     }
    420 
    421     auto make_hl = [](auto& get_regex, auto& resolve_faces) {
    422         return make_unique_ptr<DynamicRegexHighlighter<std::remove_cvref_t<decltype(get_regex)>,
    423                                                         std::remove_cvref_t<decltype(resolve_faces)>>>(
    424             std::move(get_regex), std::move(resolve_faces));
    425     };
    426     auto resolve_faces = [faces=std::move(faces)](const Regex& regex){
    427         FacesSpec spec;
    428         for (auto& face : faces)
    429         {
    430             const int capture = str_to_int_ifp(face.first).value_or_compute([&] {
    431                 return regex.named_capture_index(face.first);
    432             });
    433             if (capture < 0)
    434             {
    435                 write_to_debug_buffer(format("Error while evaluating dynamic regex expression faces,"
    436                                              " {} is neither a capture index nor a capture name",
    437                                              face.first));
    438                 return FacesSpec{};
    439             }
    440             spec.emplace_back(capture, std::move(face.second));
    441         }
    442         return spec;
    443     };
    444 
    445     CommandParser parser{params[0]};
    446     auto token = parser.read_token(true);
    447     if (token and parser.done() and token->type == Token::Type::OptionExpand and
    448         GlobalScope::instance().options()[token->content].is_of_type<Regex>())
    449     {
    450         auto get_regex = [option_name = token->content](const Context& context) {
    451             return context.options()[option_name].get<Regex>();
    452         };
    453         return make_hl(get_regex, resolve_faces);
    454     }
    455 
    456     auto get_regex = [expr = params[0]](const Context& context){
    457         try
    458         {
    459             auto re = expand(expr, context);
    460             return re.empty() ? Regex{} : Regex{re};
    461         }
    462         catch (runtime_error& err)
    463         {
    464             write_to_debug_buffer(format("Error while evaluating dynamic regex expression: {}", err.what()));
    465             return Regex{};
    466         }
    467     };
    468     return make_hl(get_regex, resolve_faces);
    469 }
    470 
    471 const HighlighterDesc line_desc = {
    472     "Parameters: <value string> <face>\n"
    473     "Highlight the line given by evaluating <value string> with <face>",
    474     {}
    475 };
    476 UniquePtr<Highlighter> create_line_highlighter(HighlighterParameters params, Highlighter*)
    477 {
    478     if (params.size() != 2)
    479         throw runtime_error("wrong parameter count");
    480 
    481     auto func = [line_expr=params[0], facespec=parse_face(params[1])]
    482                 (HighlightContext context, DisplayBuffer& display_buffer, BufferRange)
    483     {
    484         LineCount line = -1;
    485         try
    486         {
    487             line = str_to_int_ifp(expand(line_expr, context.context)).value_or(0) - 1;
    488         }
    489         catch (runtime_error& err)
    490         {
    491             write_to_debug_buffer(
    492                 format("Error evaluating highlight line expression: {}", err.what()));
    493         }
    494 
    495         if (line < 0)
    496             return;
    497 
    498         auto it = find_if(display_buffer.lines(),
    499                           [line](const DisplayLine& l)
    500                           { return l.range().begin.line == line; });
    501         if (it == display_buffer.lines().end())
    502             return;
    503 
    504         auto face = context.context.faces()[facespec];
    505         ColumnCount column = 0;
    506         for (auto& atom : *it)
    507         {
    508             column += atom.length();
    509             if (atom.has_buffer_range() and atom.begin().line != line)
    510                 break;
    511             apply_face(face)(atom);
    512         }
    513         const ColumnCount remaining = context.context.window().dimensions().column - column;
    514         if (remaining > 0)
    515             it->push_back({String{' ', remaining}, face});
    516     };
    517 
    518     return make_highlighter(std::move(func));
    519 }
    520 
    521 const HighlighterDesc column_desc = {
    522     "Parameters: [-ruler <character>] <column> <face>\n"
    523     "Highlight the column <column> with <face>",
    524     {
    525         { { "ruler", { ArgCompleter{}, "replace empty or whitespace cells with the given character. When provided, <face> is not applied to non-empty cells" } } },
    526         ParameterDesc::Flags::None, 2, 2
    527     },
    528 };
    529 UniquePtr<Highlighter> create_column_highlighter(HighlighterParameters params, Highlighter*)
    530 {
    531     ParametersParser parser{params, column_desc.params};
    532 
    533     auto positionals = parser.positionals_from(0);
    534 
    535     auto ruler = parser.get_switch("ruler");
    536     bool highlight_non_blank = not (bool)ruler;
    537     auto col_char = ruler.value_or(" ").str();
    538     if (col_char.char_length() > 1)
    539         throw runtime_error("-ruler expects a single character");
    540 
    541     auto func = [col_expr=positionals[0], facespec=parse_face(positionals[1]), highlight_non_blank, col_char]
    542                 (HighlightContext context, DisplayBuffer& display_buffer, BufferRange)
    543     {
    544         ColumnCount column = -1;
    545         try
    546         {
    547             column = str_to_int_ifp(expand(col_expr, context.context)).value_or(0) - 1;
    548         }
    549         catch (runtime_error& err)
    550         {
    551             write_to_debug_buffer(
    552                 format("Error evaluating highlight column expression: {}", err.what()));
    553         }
    554 
    555         if (column < 0)
    556             return;
    557 
    558         const auto face = context.context.faces()[facespec];
    559         if (column < context.setup.first_column or column >= context.setup.first_column + context.context.window().dimensions().column)
    560             return;
    561 
    562         column += context.setup.widget_columns - context.setup.first_column;
    563         for (auto& line : display_buffer.lines())
    564         {
    565             auto remaining_col = column;
    566             bool found = false;
    567             for (auto atom_it = line.begin(); atom_it != line.end(); ++atom_it)
    568             {
    569                 const auto atom_len = atom_it->length();
    570                 if (remaining_col < atom_len)
    571                 {
    572                     if (remaining_col > 0)
    573                         atom_it = ++line.split(atom_it, remaining_col);
    574                     if (atom_it->length() > 1)
    575                         atom_it = line.split(atom_it, 1_col);
    576                     if (highlight_non_blank)
    577                         atom_it->face = merge_faces(atom_it->face, face);
    578                     else if (is_blank(atom_it->content()[0]))
    579                     {
    580                         atom_it->replace(col_char);
    581                         atom_it->face = merge_faces(atom_it->face, face);
    582                     }
    583                     found = true;
    584                     break;
    585                 }
    586                 remaining_col -= atom_len;
    587             }
    588             if (found)
    589                 continue;
    590 
    591             if (remaining_col > 0)
    592                 line.push_back({String{' ', remaining_col}, Face{}});
    593             line.push_back({col_char, face});
    594         }
    595     };
    596 
    597     return make_highlighter(std::move(func));
    598 }
    599 
    600 const HighlighterDesc wrap_desc = {
    601     "Parameters: [-word] [-indent] [-width <max_width>] [-marker <marker_text>]\n"
    602     "Wrap lines to window width",
    603     { {
    604         { "word",   { {}, "wrap at word boundaries instead of codepoint boundaries" } },
    605         { "indent", { {}, "preserve line indentation of the wrapped line" } },
    606         { "width",  { ArgCompleter{}, "wrap at the given column instead of the window's width" } },
    607         { "marker", { ArgCompleter{}, "insert the given text at the beginning of the wrapped line" } }, },
    608         ParameterDesc::Flags::None, 0, 0
    609     }
    610 };
    611 struct WrapHighlighter : Highlighter
    612 {
    613     WrapHighlighter(ColumnCount max_width, bool word_wrap, bool preserve_indent, String marker)
    614         : Highlighter{HighlightPass::Wrap}, m_word_wrap{word_wrap},
    615           m_preserve_indent{preserve_indent}, m_max_width{max_width},
    616           m_marker{std::move(marker)} {}
    617 
    618     static constexpr StringView ms_id = "wrap";
    619 
    620     struct SplitPos{ DisplayLine::iterator atom_it; ByteCount byte; ColumnCount column; };
    621 
    622     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
    623     {
    624         if (contains(context.disabled_ids, ms_id))
    625             return;
    626 
    627         const ColumnCount wrap_column = std::min(m_max_width, context.context.window().dimensions().column - context.setup.widget_columns);
    628         if (wrap_column <= 0)
    629             return;
    630 
    631         const Buffer& buffer = context.context.buffer();
    632         const int tabstop = context.context.options()["tabstop"].get<int>();
    633         const ColumnCount marker_len = zero_if_greater(m_marker.column_length(), wrap_column);
    634         const Face face_marker = context.context.faces()["WrapMarker"];
    635         for (auto it = display_buffer.lines().begin();
    636              it != display_buffer.lines().end(); ++it)
    637         {
    638             const ColumnCount indent = m_preserve_indent ?
    639                 zero_if_greater(line_indent(buffer, tabstop, it->range().begin.line), wrap_column) : 0_col;
    640             const ColumnCount prefix_len = std::max(marker_len, indent);
    641 
    642             SplitPos pos{it->begin(), 0, 0}; ;
    643             while (next_split_pos(pos, it->end(), wrap_column, prefix_len))
    644             {
    645                 auto& line = *it;
    646 
    647                 if (pos.byte > 0)
    648                     pos.atom_it = ++line.split(pos.atom_it, pos.atom_it->begin() + BufferCoord{0, pos.byte});
    649 
    650                 auto coord = pos.atom_it->begin();
    651                 DisplayLine new_line{AtomList{std::make_move_iterator(pos.atom_it), std::make_move_iterator(line.end())}};
    652                 line.erase(pos.atom_it, line.end());
    653                 auto next_atom_it = new_line.begin();
    654 
    655                 if (marker_len != 0)
    656                     next_atom_it = ++new_line.insert(new_line.begin(), {m_marker, face_marker});
    657                 if (indent > marker_len)
    658                 {
    659                     next_atom_it = new_line.insert(next_atom_it, {buffer, {coord, coord}});
    660                     next_atom_it->replace(String{' ', indent - marker_len});
    661                     ++next_atom_it;
    662                 }
    663 
    664                 it = display_buffer.lines().insert(it+1, std::move(new_line));
    665                 pos = SplitPos{next_atom_it, 0, std::max(marker_len, indent)};
    666             }
    667         }
    668     }
    669 
    670     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
    671     {
    672         if (contains(context.disabled_ids, ms_id))
    673             return;
    674 
    675         const ColumnCount wrap_column = std::min(m_max_width, context.context.window().dimensions().column - setup.widget_columns);
    676         if (wrap_column <= 0)
    677             return;
    678 
    679         // Disable horizontal scrolling when using a WrapHighlighter
    680         setup.first_column = 0;
    681         setup.scroll_offset.column = 0;
    682     }
    683 
    684     void fill_unique_ids(Vector<StringView>& unique_ids) const override
    685     {
    686         unique_ids.push_back(ms_id);
    687     }
    688 
    689     bool next_split_pos(SplitPos& pos, DisplayLine::iterator line_end,
    690                         ColumnCount wrap_column, ColumnCount prefix_len) const
    691     {
    692         SplitPos last_word_boundary{};
    693         SplitPos last_WORD_boundary{};
    694 
    695         auto update_word_boundaries = [&](Codepoint cp) {
    696             if (m_word_wrap and not is_word<Word>(cp))
    697                 last_word_boundary = pos;
    698             if (m_word_wrap and not is_word<WORD>(cp))
    699                 last_WORD_boundary = pos;
    700         };
    701 
    702         if (pos.atom_it->type() != DisplayAtom::Range and
    703             pos.column + pos.atom_it->length() >= wrap_column)
    704             return ++pos.atom_it != line_end;
    705 
    706         while (pos.atom_it != line_end and pos.column < wrap_column)
    707         {
    708             auto content = pos.atom_it->content();
    709             const char* it = &content[pos.byte];
    710             const Codepoint cp = utf8::read_codepoint(it, content.end());
    711             const ColumnCount width = codepoint_width(cp);
    712             if (pos.column + width > wrap_column) // the target column was in the char
    713             {
    714                 update_word_boundaries(cp);
    715                 break;
    716             }
    717             pos.column += width;
    718             pos.byte = (int)(it - content.begin());
    719             update_word_boundaries(cp);
    720             if (it == content.end())
    721             {
    722                 ++pos.atom_it;
    723                 pos.byte = 0;
    724 
    725                 if (pos.atom_it != line_end and pos.atom_it->type() != DisplayAtom::Range and
    726                     pos.column + pos.atom_it->length() >= wrap_column)
    727                     return true;
    728 
    729                 // Thanks to the pass ordering, atom boundary should always be reasonable word split points
    730                 last_word_boundary = pos;
    731                 last_WORD_boundary = pos;
    732             }
    733         }
    734         if (pos.atom_it == line_end)
    735             return false;
    736 
    737         auto content = pos.atom_it->content();
    738         if (m_word_wrap and pos.byte < content.length())
    739         {
    740             auto find_split_pos = [&](SplitPos start_pos, auto is_word) {
    741                 if (start_pos.column == 0)
    742                     return false;
    743                 const char* it = &content[pos.byte];
    744                 // split at current position if is a word boundary
    745                 if (not is_word(utf8::codepoint(it, content.end()), {'_'}))
    746                     return true;
    747                 // split at last word boundary if the word is shorter than our wrapping width
    748                 ColumnCount word_length = pos.column - start_pos.column;
    749                 ColumnCount max_word_length = wrap_column - prefix_len;
    750                 while (it != content.end() and word_length <= max_word_length)
    751                 {
    752                     const Codepoint cp = utf8::read_codepoint(it, content.end());
    753                     if (not is_word(cp, {'_'}))
    754                         break;
    755                     word_length += codepoint_width(cp);
    756                 }
    757                 if (word_length <= max_word_length)
    758                 {
    759                     pos = start_pos;
    760                     return true;
    761                 }
    762                 return false;
    763             };
    764             if (find_split_pos(last_WORD_boundary, is_word<WORD>) or
    765                 find_split_pos(last_word_boundary, is_word<Word>))
    766                 return true;
    767         }
    768 
    769         return true;
    770     }
    771 
    772     static ColumnCount line_indent(const Buffer& buffer, int tabstop, LineCount line)
    773     {
    774         StringView l = buffer[line];
    775         auto col = 0_byte;
    776         while (is_horizontal_blank(l[col]))
    777                ++col;
    778         return get_column(buffer, tabstop, {line, col});
    779     }
    780 
    781     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
    782     {
    783         ParametersParser parser(params, wrap_desc.params);
    784         ColumnCount max_width = parser.get_switch("width").map(str_to_int)
    785             .value_or(std::numeric_limits<int>::max());
    786 
    787         return make_unique_ptr<WrapHighlighter>(max_width, (bool)parser.get_switch("word"),
    788                                                  (bool)parser.get_switch("indent"),
    789                                                  parser.get_switch("marker").value_or("").str());
    790     }
    791 
    792     static ColumnCount zero_if_greater(ColumnCount val, ColumnCount max) { return val < max ? val : 0; };
    793 
    794     const bool m_word_wrap;
    795     const bool m_preserve_indent;
    796     const ColumnCount m_max_width;
    797     const String m_marker;
    798 };
    799 
    800 struct TabulationHighlighter : Highlighter
    801 {
    802     TabulationHighlighter() : Highlighter{HighlightPass::Replace} {}
    803 
    804     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
    805     {
    806         const ColumnCount tabstop = context.context.options()["tabstop"].get<int>();
    807         const auto& buffer = context.context.buffer();
    808         for (auto& line : display_buffer.lines())
    809         {
    810             ColumnCount column = 0;
    811             const char* line_data = nullptr;
    812             const char* pos = nullptr;
    813             for (auto atom_it = line.begin(); atom_it != line.end(); ++atom_it)
    814             {
    815                 if (atom_it->type() != DisplayAtom::Range)
    816                     continue;
    817 
    818                 auto begin = atom_it->begin();
    819                 if (auto* atom_line_data = buffer[begin.line].data(); atom_line_data != line_data)
    820                 {
    821                     pos = line_data = atom_line_data;
    822                     column = 0;
    823                 }
    824 
    825                 kak_assert(pos != nullptr and pos <= line_data + begin.column);
    826                 for (auto end = line_data + atom_it->end().column; pos != end; ++pos)
    827                 {
    828                     const char* next_tab = std::find(pos, end, '\t');
    829                     if (next_tab == end)
    830                     {
    831                         pos = end;
    832                         break;
    833                     }
    834 
    835                     while (pos != next_tab)
    836                         column += codepoint_width(utf8::read_codepoint(pos, next_tab));
    837                     const ColumnCount tabwidth = tabstop - (column % tabstop);
    838                     column += tabwidth;
    839 
    840                     if (pos >= line_data + atom_it->begin().column)
    841                     {
    842                         if (pos != line_data + atom_it->begin().column)
    843                             atom_it = ++line.split(atom_it, {begin.line, ByteCount(pos - line_data)});
    844                         if (pos + 1 != end)
    845                             atom_it = line.split(atom_it, {begin.line, ByteCount(pos + 1 - line_data)});
    846 
    847                         atom_it->replace(String{' ', tabwidth});
    848                         ++atom_it;
    849                     }
    850                 }
    851 
    852                 if (atom_it == line.end())
    853                     break;
    854             }
    855         }
    856     }
    857 
    858     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
    859     {
    860         auto& buffer = context.context.buffer();
    861         // Ensure that a cursor on a tab character makes the full tab character visible
    862         auto cursor = context.context.selections().main().cursor();
    863         if (buffer.byte_at(cursor) != '\t')
    864             return;
    865 
    866         const ColumnCount tabstop = context.context.options()["tabstop"].get<int>();
    867         const ColumnCount column = get_column(buffer, tabstop, cursor);
    868         const ColumnCount width = tabstop - (column % tabstop);
    869         const ColumnCount win_end = setup.first_column + context.context.window().dimensions().column - setup.widget_columns;
    870         const ColumnCount offset = std::max(column + width - win_end, 0_col);
    871 
    872         setup.first_column += offset;
    873     }
    874 };
    875 
    876 const HighlighterDesc show_whitespace_desc = {
    877     "Parameters: [-tab <separator>] [-tabpad <separator>] [-lf <separator>] [-spc <separator>] [-nbsp <separator>] [-indent <separator>]\n"
    878     "Display whitespaces using symbols",
    879     { {
    880         { "tab",    { ArgCompleter{}, "replace tabulations with the given character" } },
    881         { "tabpad", { ArgCompleter{}, "append as many of the given character as is necessary to honor `tabstop`" } },
    882         { "spc",    { ArgCompleter{}, "replace spaces with the given character" } },
    883         { "lf",     { ArgCompleter{}, "replace line feeds with the given character" } },
    884         { "nbsp",   { ArgCompleter{}, "replace non-breakable spaces with the given character" } },
    885         { "indent", { ArgCompleter{}, "replace first space of every indent with the given character according to `indentwidth`" } },
    886         { "only-trailing", { {}, "only highlighting trailing whitespaces" } } },
    887         ParameterDesc::Flags::None, 0, 0
    888     }
    889 };
    890 struct ShowWhitespacesHighlighter : Highlighter
    891 {
    892     ShowWhitespacesHighlighter(String tab, String tabpad, String spc, String lf, String nbsp, String indent, bool only_trailing)
    893       : Highlighter{HighlightPass::Replace}, m_tab{std::move(tab)}, m_tabpad{std::move(tabpad)},
    894         m_spc{std::move(spc)}, m_lf{std::move(lf)}, m_nbsp{std::move(nbsp)}, m_indent{std::move(indent)}, m_only_trailing{std::move(only_trailing)}
    895     {}
    896 
    897     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
    898     {
    899         ParametersParser parser(params, show_whitespace_desc.params);
    900 
    901         bool only_trailing = (bool) parser.get_switch("only-trailing");
    902         auto get_param = [&](StringView param,  StringView fallback) {
    903             StringView value = parser.get_switch(param).value_or(fallback);
    904             if (value.char_length() > 1)
    905                 throw runtime_error{format("-{} expects a single character or empty parameter", param)};
    906             return value.str();
    907         };
    908 
    909         return make_unique_ptr<ShowWhitespacesHighlighter>(
    910             get_param("tab", "→"), get_param("tabpad", " "), get_param("spc", "·"),
    911             get_param("lf", "¬"), get_param("nbsp", "⍽"), get_param("indent", "│"), only_trailing);
    912     }
    913 
    914 private:
    915     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
    916     {
    917         const int tabstop = context.context.options()["tabstop"].get<int>();
    918         const int indentwidth = context.context.options()["indentwidth"].get<int>();
    919         auto whitespaceface = context.context.faces()["Whitespace"];
    920         auto indentface = context.context.faces()["WhitespaceIndent"];
    921         const auto& buffer = context.context.buffer();
    922         for (auto& line : display_buffer.lines())
    923         {
    924             bool is_indentation = true;
    925             for (auto atom_it = line.begin(); atom_it != line.end(); ++atom_it)
    926             {
    927                 if (atom_it->type() != DisplayAtom::Range)
    928                     continue;
    929 
    930                 auto begin = get_iterator(buffer, atom_it->begin());
    931                 auto end = get_iterator(buffer, atom_it->end());
    932                 auto last_non_space = begin.coord();
    933 
    934                 auto is_whitespace = [](Codepoint cp) {
    935                     return cp == '\t' or cp == ' ' or cp == '\n' or cp == 0xA0 or cp == 0x202F;
    936                 };
    937 
    938                 if(m_only_trailing)
    939                 {
    940                     for (BufferIterator it = begin; it != end; )
    941                     {
    942                         if (not is_whitespace(utf8::read_codepoint(it, end)))
    943                             last_non_space = it.coord();
    944                     }
    945                 }
    946 
    947                 for (BufferIterator it = begin; it != end; )
    948                 {
    949                     auto coord = it.coord();
    950                     Codepoint cp = utf8::read_codepoint(it, end);
    951                     auto face = whitespaceface;
    952                     if (is_whitespace(cp))
    953                     {
    954                         if (m_only_trailing and it.coord() <= last_non_space)
    955                             continue;
    956 
    957                         if (coord != begin.coord())
    958                             atom_it = ++line.split(atom_it, coord);
    959                         if (it != end)
    960                             atom_it = line.split(atom_it, it.coord());
    961 
    962                         if (cp == '\t' and not m_tab.empty() and not m_tabpad.empty())
    963                         {
    964                             const ColumnCount column = get_column(buffer, tabstop, coord);
    965                             const ColumnCount count = tabstop - (column % tabstop);
    966                             atom_it->replace(m_tab + String(m_tabpad[(CharCount)0], count - m_tab.column_length()));
    967                         }
    968                         else if (cp == ' ' and is_indentation and indentwidth > 0 and not m_indent.empty()) {
    969                             const ColumnCount column = get_column(buffer, tabstop, coord);
    970                             if (column % indentwidth == 0 and column != 0) {
    971                                 atom_it->replace(m_indent);
    972                                 face = indentface;
    973                             }
    974                             else {
    975                                 atom_it->replace(m_spc);
    976                             }
    977                         }
    978                         else if (cp == ' ' and not m_spc.empty()) {
    979                             atom_it->replace(m_spc);
    980                         }
    981                         else if (cp == '\n' and not m_lf.empty())
    982                             atom_it->replace(m_lf);
    983                         else if ((cp == 0xA0 or cp == 0x202F) and not m_nbsp.empty())
    984                             atom_it->replace(m_nbsp);
    985                         atom_it->face = merge_faces(atom_it->face, face);
    986                         break;
    987                     }
    988                     else
    989                     {
    990                         is_indentation = false;
    991                     }
    992                 }
    993             }
    994         }
    995     }
    996 
    997     const String m_tab, m_tabpad, m_spc, m_lf, m_nbsp, m_indent;
    998     const bool m_only_trailing;
    999 };
   1000 
   1001 const HighlighterDesc line_numbers_desc = {
   1002     "Parameters: [-relative] [-hlcursor] [-separators <separator|separator:cursor|cursor:up:down>] [-min-digits <cols>]\n"
   1003     "Display line numbers",
   1004     { {
   1005         { "relative", { {}, "show line numbers relative to the main cursor line" } },
   1006         { "full-relative", { {}, "show line numbers relative to the main cursor line and the main cursor line as 0" } },
   1007         { "separator", { ArgCompleter{}, "string to separate the line numbers column from the rest of the buffer (default '|')" } },
   1008         { "cursor-separator", { ArgCompleter{}, "identical to -separator but applies only to the line of the cursor (default is the same value passed to -separator)" } },
   1009         { "min-digits", { ArgCompleter{}, "use at least the given number of columns to display line numbers (default 2)" } },
   1010         { "hlcursor", { {}, "highlight the cursor line with a separate face" } } },
   1011         ParameterDesc::Flags::None, 0, 0
   1012     }
   1013 };
   1014 struct LineNumbersHighlighter : Highlighter
   1015 {
   1016     LineNumbersHighlighter(bool relative, bool zero_cursor_line, bool hl_cursor_line, String separator, String cursor_separator, int min_digits)
   1017       : Highlighter{HighlightPass::Move},
   1018         m_relative{relative},
   1019         m_zero_cursor_line{zero_cursor_line},
   1020         m_hl_cursor_line{hl_cursor_line},
   1021         m_separator{std::move(separator)},
   1022         m_cursor_separator{std::move(cursor_separator)},
   1023         m_min_digits{min_digits} {}
   1024 
   1025     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
   1026     {
   1027         ParametersParser parser(params, line_numbers_desc.params);
   1028 
   1029         StringView separator = parser.get_switch("separator").value_or("│");
   1030         StringView cursor_separator = parser.get_switch("cursor-separator").value_or(separator);
   1031 
   1032         if (separator.length() > 10)
   1033             throw runtime_error("separator length is limited to 10 bytes");
   1034 
   1035         if (cursor_separator.column_length() != separator.column_length())
   1036             throw runtime_error("separator for active line should have the same length as 'separator'");
   1037 
   1038         int min_digits = parser.get_switch("min-digits").map(str_to_int).value_or(2);
   1039         if (min_digits < 0)
   1040             throw runtime_error("min digits must be positive");
   1041         if (min_digits > 10)
   1042             throw runtime_error("min digits is limited to 10");
   1043         const bool relative = (bool)parser.get_switch("relative");
   1044         const bool full_relative = (bool)parser.get_switch("full-relative");
   1045         return make_unique_ptr<LineNumbersHighlighter>(relative or full_relative, full_relative, (bool)parser.get_switch("hlcursor"), separator.str(), cursor_separator.str(), min_digits);
   1046     }
   1047 
   1048 private:
   1049     static constexpr StringView ms_id = "line-numbers";
   1050 
   1051     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
   1052     {
   1053         if (contains(context.disabled_ids, ms_id))
   1054             return;
   1055 
   1056         const auto& faces = context.context.faces();
   1057         const Face face = faces["LineNumbers"];
   1058         const Face face_wrapped = faces["LineNumbersWrapped"];
   1059         const Face face_absolute = faces["LineNumberCursor"];
   1060         int digit_count = compute_digit_count(context);
   1061 
   1062         char format[16];
   1063         format_to(format, "\\{:{}}", digit_count);
   1064         const int main_line = (int)context.context.selections().main().cursor().line + 1;
   1065         int last_line = -1;
   1066         for (auto& line : display_buffer.lines())
   1067         {
   1068             const int current_line = (int)line.range().begin.line + 1;
   1069             const bool is_cursor_line = main_line == current_line;
   1070             const int line_to_format = (m_relative and (not is_cursor_line or m_zero_cursor_line)) ?
   1071                                        current_line - main_line : current_line;
   1072             char buffer[16];
   1073             format_to(buffer, format, std::abs(line_to_format));
   1074             const auto atom_face = last_line == current_line ? face_wrapped :
   1075                 ((m_hl_cursor_line and is_cursor_line) ? face_absolute : face);
   1076 
   1077             const auto& separator = is_cursor_line and last_line != current_line
   1078                                     ? m_cursor_separator : m_separator;
   1079 
   1080             line.insert(line.begin(), {buffer, atom_face});
   1081             line.insert(line.begin() + 1, {separator, face});
   1082 
   1083             last_line = current_line;
   1084         }
   1085     }
   1086 
   1087     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
   1088     {
   1089         if (contains(context.disabled_ids, ms_id))
   1090             return;
   1091 
   1092         ColumnCount width = compute_digit_count(context) + m_separator.column_length();
   1093         setup.widget_columns += width;
   1094     }
   1095 
   1096     void fill_unique_ids(Vector<StringView>& unique_ids) const override
   1097     {
   1098         unique_ids.push_back(ms_id);
   1099     }
   1100 
   1101     int compute_digit_count(const HighlightContext& context) const
   1102     {
   1103         int digit_count = 0;
   1104         auto cursor_line = context.context.selections().main().cursor().line + 1;
   1105         LineCount line_count = (m_relative and m_zero_cursor_line)
   1106             ? std::max(abs(context.setup.first_line - cursor_line),
   1107                        abs(context.setup.first_line + context.setup.line_count - cursor_line))
   1108             : context.context.buffer().line_count();
   1109         for (LineCount c = line_count; c > 0; c /= 10)
   1110             ++digit_count;
   1111         return std::max(digit_count, m_min_digits);
   1112     }
   1113 
   1114     const bool m_relative;
   1115     const bool m_zero_cursor_line;
   1116     const bool m_hl_cursor_line;
   1117     const String m_separator;
   1118     const String m_cursor_separator;
   1119     const int m_min_digits;
   1120 };
   1121 
   1122 const HighlighterDesc show_matching_desc = {
   1123     "Apply the MatchingChar face to the char matching the one under the cursor",
   1124     { { { "previous", {} } }, ParameterDesc::Flags::SwitchesOnlyAtStart, 0, 0 }
   1125 };
   1126 template<bool match_prev>
   1127 void show_matching_char(HighlightContext context, DisplayBuffer& display_buffer, BufferRange)
   1128 {
   1129     const Face face = context.context.faces()["MatchingChar"];
   1130     const auto& matching_pairs = context.context.options()["matching_pairs"].get<Vector<Codepoint, MemoryDomain::Options>>();
   1131     const auto range = display_buffer.range();
   1132     const auto& buffer = context.context.buffer();
   1133     for (auto& sel : context.context.selections())
   1134     {
   1135         auto pos = sel.cursor();
   1136         if (pos < range.begin or pos >= range.end)
   1137             continue;
   1138 
   1139         utf8::iterator it{buffer.iterator_at(pos), buffer};
   1140         auto match = find(matching_pairs, *it);
   1141         bool matching_prev = match == matching_pairs.end() and match_prev;
   1142         if (matching_prev)
   1143             match = find(matching_pairs, *--it);
   1144 
   1145         if (match == matching_pairs.end())
   1146             continue;
   1147 
   1148         if (matching_prev)
   1149             highlight_range(display_buffer, it.base().coord(), (it+1).base().coord(),
   1150                             false, apply_face(face));
   1151 
   1152         int level = 0;
   1153         if (((match - matching_pairs.begin()) % 2) == 0)
   1154         {
   1155             const Codepoint opening = *match;
   1156             const Codepoint closing = *(match+1);
   1157             while (it.base().coord() <= range.end)
   1158             {
   1159                 if (*it == opening)
   1160                     ++level;
   1161                 else if (*it == closing and --level == 0)
   1162                 {
   1163                     highlight_range(display_buffer, it.base().coord(), (it+1).base().coord(),
   1164                                     false, apply_face(face));
   1165                     break;
   1166                 }
   1167                 ++it;
   1168             }
   1169         }
   1170         else if (pos > range.begin)
   1171         {
   1172             const Codepoint opening = *(match-1);
   1173             const Codepoint closing = *match;
   1174             while (true)
   1175             {
   1176                 if (*it == closing)
   1177                     ++level;
   1178                 else if (*it == opening and --level == 0)
   1179                 {
   1180                     highlight_range(display_buffer, it.base().coord(), (it+1).base().coord(),
   1181                                     false, apply_face(face));
   1182                     break;
   1183                 }
   1184                 if (it.base().coord() <= range.begin)
   1185                     break;
   1186                 --it;
   1187             }
   1188         }
   1189     }
   1190 }
   1191 
   1192 UniquePtr<Highlighter> create_matching_char_highlighter(HighlighterParameters params, Highlighter*)
   1193 {
   1194     ParametersParser parser{params, show_matching_desc.params};
   1195     return make_highlighter(parser.get_switch("previous") ? show_matching_char<true> : show_matching_char<false>);
   1196 }
   1197 
   1198 void highlight_selections(HighlightContext context, DisplayBuffer& display_buffer, BufferRange)
   1199 {
   1200     const auto& buffer = context.context.buffer();
   1201     const auto& faces = context.context.faces();
   1202     const Face sel_faces[6] = {
   1203             faces["PrimarySelection"], faces["SecondarySelection"],
   1204             faces["PrimaryCursor"],    faces["SecondaryCursor"],
   1205             faces["PrimaryCursorEol"], faces["SecondaryCursorEol"],
   1206     };
   1207 
   1208     const auto& selections = context.context.selections();
   1209     for (size_t i = 0; i < selections.size(); ++i)
   1210     {
   1211         auto& sel = selections[i];
   1212         const bool forward = sel.anchor() <= sel.cursor();
   1213         BufferCoord begin = forward ? sel.anchor() : buffer.char_next(sel.cursor());
   1214         BufferCoord end   = forward ? (BufferCoord)sel.cursor() : buffer.char_next(sel.anchor());
   1215 
   1216         const bool primary = (i == selections.main_index());
   1217         highlight_range(display_buffer, begin, end, false,
   1218                         apply_face(sel_faces[primary ? 0 : 1]));
   1219     }
   1220     for (size_t i = 0; i < selections.size(); ++i)
   1221     {
   1222         auto& sel = selections[i];
   1223         const BufferCoord coord = sel.cursor();
   1224         const bool primary = (i == selections.main_index());
   1225         const bool eol = buffer[coord.line].length() - 1 == coord.column;
   1226         highlight_range(display_buffer, coord, buffer.char_next(coord), false,
   1227                         apply_face(sel_faces[2 + (eol ? 2 : 0) + (primary ? 0 : 1)]));
   1228     }
   1229 }
   1230 
   1231 void expand_unprintable(HighlightContext context, DisplayBuffer& display_buffer, BufferRange)
   1232 {
   1233     auto is_printable = [](Codepoint cp) { // follow musl iswprint set of printable characters, but with straightforward impl
   1234         if (cp < 0xff)
   1235             return cp == '\n' or cp >= ' ';
   1236         else if (cp == 0x2028 or cp == 0x2029 or (cp >= 0xFFF9 and cp <= 0xFFFB))
   1237             return false;
   1238         return true;
   1239     };
   1240     const auto& buffer = context.context.buffer();
   1241     auto error = context.context.faces()[FaceSpec{{}, "Error"}];
   1242     for (auto& line : display_buffer.lines())
   1243     {
   1244         for (auto atom_it = line.begin(); atom_it != line.end(); ++atom_it)
   1245         {
   1246             if (atom_it->type() != DisplayAtom::Range)
   1247                 continue;
   1248 
   1249             auto begin = atom_it->begin();
   1250             auto line_data = buffer[begin.line].data();
   1251             for (auto it  = line_data + begin.column, end = line_data + atom_it->end().column; it < end;)
   1252             {
   1253                 auto next = it;
   1254                 Codepoint cp = utf8::read_codepoint(next, end);
   1255                 if (not is_printable(cp))
   1256                 {
   1257                     if (ByteCount pos(it - line_data); pos != begin.column)
   1258                         atom_it = ++line.split(atom_it, {begin.line, pos});
   1259                     if (ByteCount pos(next - line_data); pos < atom_it->end().column)
   1260                         atom_it = line.split(atom_it, {begin.line, pos});
   1261 
   1262                     atom_it->replace("�");
   1263                     atom_it->face = error;
   1264                     break;
   1265                 }
   1266                 it = next;
   1267             }
   1268         }
   1269     }
   1270 }
   1271 
   1272 static void update_line_specs_ifn(const Buffer& buffer, LineAndSpecList& line_flags)
   1273 {
   1274     if (line_flags.prefix == buffer.timestamp())
   1275         return;
   1276 
   1277     auto& lines = line_flags.list;
   1278 
   1279     auto modifs = compute_line_modifications(buffer, line_flags.prefix);
   1280     auto ins_pos = lines.begin();
   1281     for (auto it = lines.begin(); it != lines.end(); ++it)
   1282     {
   1283         auto& line = std::get<0>(*it); // that line is 1 based as it comes from user side
   1284         auto modif_it = std::upper_bound(modifs.begin(), modifs.end(), line-1,
   1285                                          [](const LineCount& l, const LineModification& c)
   1286                                          { return l < c.old_line; });
   1287         if (modif_it != modifs.begin())
   1288         {
   1289             auto& prev = *(modif_it-1);
   1290             if (line-1 < prev.old_line + prev.num_removed)
   1291                 continue; // line removed
   1292 
   1293             line += prev.diff();
   1294         }
   1295 
   1296         if (ins_pos != it)
   1297             *ins_pos = std::move(*it);
   1298         ++ins_pos;
   1299     }
   1300     lines.erase(ins_pos, lines.end());
   1301     line_flags.prefix = buffer.timestamp();
   1302 }
   1303 
   1304 void option_update(LineAndSpecList& opt, const Context& context)
   1305 {
   1306     update_line_specs_ifn(context.buffer(), opt);
   1307 }
   1308 
   1309 void option_list_postprocess(Vector<LineAndSpec, MemoryDomain::Options>& opt)
   1310 {
   1311     std::sort(opt.begin(), opt.end(),
   1312               [](auto& lhs, auto& rhs)
   1313               { return std::get<0>(lhs) < std::get<0>(rhs); });
   1314 }
   1315 
   1316 const HighlighterDesc flag_lines_desc = {
   1317     "Parameters: <face> <option name>\n"
   1318     "Display flags specified in the line-spec option <option name> with <face>",
   1319     {}
   1320 };
   1321 struct FlagLinesHighlighter : Highlighter
   1322 {
   1323     FlagLinesHighlighter(String option_name, String default_face, bool after)
   1324         : Highlighter{HighlightPass::Move},
   1325           m_option_name{std::move(option_name)},
   1326           m_default_face{std::move(default_face)},
   1327           m_after(after) {}
   1328 
   1329     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
   1330     {
   1331         ParametersParser parser{params, {
   1332             {{"after", {{}, "display at line end" }}},
   1333             ParameterDesc::Flags::SwitchesOnlyAtStart, 2, 2
   1334         }};
   1335 
   1336         const String& default_face = parser[0];
   1337         const String& option_name = parser[1];
   1338 
   1339         // throw if wrong option type
   1340         GlobalScope::instance().options()[option_name].get<LineAndSpecList>();
   1341 
   1342         return make_unique_ptr<FlagLinesHighlighter>(option_name, default_face, (bool)parser.get_switch("after"));
   1343     }
   1344 
   1345 private:
   1346     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
   1347     {
   1348         auto& line_flags = context.context.options()[m_option_name].get_mutable<LineAndSpecList>();
   1349         const auto& buffer = context.context.buffer();
   1350         update_line_specs_ifn(buffer, line_flags);
   1351 
   1352         auto def_face = context.context.faces()[m_default_face];
   1353         Vector<DisplayLine> display_lines;
   1354         auto& lines = line_flags.list;
   1355         try
   1356         {
   1357             for (auto& line : lines)
   1358             {
   1359                 display_lines.push_back(parse_display_line(std::get<1>(line), context.context.faces()));
   1360                 for (auto& atom : display_lines.back())
   1361                     atom.face = merge_faces(def_face, atom.face);
   1362             }
   1363         }
   1364         catch (runtime_error& err)
   1365         {
   1366             write_to_debug_buffer(format("Error while evaluating line flag: {}", err.what()));
   1367             return;
   1368         }
   1369 
   1370         ColumnCount width = 0;
   1371         for (auto& l : display_lines)
   1372              width = std::max(width, l.length());
   1373         const DisplayAtom empty{String{' ', width}, def_face};
   1374         for (auto& line : display_buffer.lines())
   1375         {
   1376             int line_num = (int)line.range().begin.line + 1;
   1377             auto it = find_if(lines,
   1378                               [&](const LineAndSpec& l)
   1379                               { return std::get<0>(l) == line_num; });
   1380             if (m_after)
   1381             {
   1382                 if (it != lines.end())
   1383                 {
   1384                     DisplayLine& display_line = display_lines[it - lines.begin()];
   1385                     std::copy(std::make_move_iterator(display_line.begin()),
   1386                               std::make_move_iterator(display_line.end()),
   1387                               std::inserter(line, line.end()));
   1388                 }
   1389                 continue;
   1390             }
   1391             if (it == lines.end())
   1392                 line.insert(line.begin(), empty);
   1393             else
   1394             {
   1395                 DisplayLine& display_line = display_lines[it - lines.begin()];
   1396                 DisplayAtom padding_atom{String(' ', width - display_line.length()), def_face};
   1397                 auto it = std::copy(std::make_move_iterator(display_line.begin()),
   1398                                     std::make_move_iterator(display_line.end()),
   1399                                     std::inserter(line, line.begin()));
   1400 
   1401                 if (padding_atom.length() != 0)
   1402                     *it++ = std::move(padding_atom);
   1403             }
   1404         }
   1405     }
   1406 
   1407     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
   1408     {
   1409         if (m_after)
   1410             return;
   1411 
   1412         auto& line_flags = context.context.options()[m_option_name].get_mutable<LineAndSpecList>();
   1413         const auto& buffer = context.context.buffer();
   1414         update_line_specs_ifn(buffer, line_flags);
   1415 
   1416         ColumnCount width = 0;
   1417         try
   1418         {
   1419             for (auto& line : line_flags.list)
   1420                 width = std::max(parse_display_line(std::get<1>(line), context.context.faces()).length(), width);
   1421         }
   1422         catch (runtime_error& err)
   1423         {
   1424             write_to_debug_buffer(format("Error while evaluating line flag: {}", err.what()));
   1425             return;
   1426         }
   1427 
   1428         setup.widget_columns += width;
   1429     }
   1430 
   1431     String m_option_name;
   1432     String m_default_face;
   1433     bool m_after;
   1434 };
   1435 
   1436 bool is_empty(const InclusiveBufferRange& range)
   1437 {
   1438     return range.last < BufferCoord{0,0};
   1439 }
   1440 
   1441 String option_to_string(InclusiveBufferRange range)
   1442 {
   1443     if (is_empty(range))
   1444         return format("{}.{}+0", range.first.line+1, range.first.column+1);
   1445     return format("{}.{},{}.{}",
   1446                   range.first.line+1, range.first.column+1,
   1447                   range.last.line+1, range.last.column+1);
   1448 }
   1449 
   1450 InclusiveBufferRange option_from_string(Meta::Type<InclusiveBufferRange>, StringView str)
   1451 {
   1452     auto sep = find_if(str, [](char c){ return c == ',' or c == '+'; });
   1453     auto dot_beg = find(StringView{str.begin(), sep}, '.');
   1454     auto dot_end = find(StringView{sep, str.end()}, '.');
   1455 
   1456     if (sep == str.end() or dot_beg == sep or
   1457         (*sep == ',' and dot_end == str.end()))
   1458         throw runtime_error(format("'{}' does not follow <line>.<column>,<line>.<column> or <line>.<column>+<len> format", str));
   1459 
   1460     const BufferCoord first{str_to_int({str.begin(), dot_beg}) - 1,
   1461                             str_to_int({dot_beg+1, sep}) - 1};
   1462 
   1463     if (first.line < 0 or first.column < 0)
   1464         throw runtime_error("coordinates elements should be >= 1");
   1465 
   1466     if (*sep == '+')
   1467     {
   1468         auto len = str_to_int({sep+1, str.end()});
   1469         return {first, len == 0 ? BufferCoord{-1,-1} : BufferCoord{first.line, first.column + len - 1}};
   1470     }
   1471 
   1472     const BufferCoord last{str_to_int({sep+1, dot_end}) - 1, str_to_int({dot_end+1, str.end()}) - 1};
   1473     if (last.line < 0 or last.column < 0)
   1474         throw runtime_error("coordinates elements should be >= 1");
   1475 
   1476     return { std::min(first, last), std::max(first, last) };
   1477 }
   1478 
   1479 template<typename OptionType, typename DerivedType, HighlightPass pass = HighlightPass::Colorize>
   1480 struct OptionBasedHighlighter : Highlighter
   1481 {
   1482     OptionBasedHighlighter(String option_name)
   1483         : Highlighter{pass}
   1484         , m_option_name{std::move(option_name)} {}
   1485 
   1486     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
   1487     {
   1488         if (params.size() != 1)
   1489             throw runtime_error("wrong parameter count");
   1490 
   1491         const String& option_name = params[0];
   1492         // throw if wrong option type
   1493         GlobalScope::instance().options()[option_name].get<OptionType>();
   1494 
   1495         return make_unique_ptr<DerivedType>(option_name);
   1496     }
   1497 
   1498     OptionType& get_option(const HighlightContext& context) const
   1499     {
   1500         return context.context.options()[m_option_name].template get_mutable<OptionType>();
   1501     }
   1502 
   1503 private:
   1504     const String m_option_name;
   1505 };
   1506 
   1507 BufferCoord& get_first(RangeAndString& r) { return std::get<0>(r).first; }
   1508 BufferCoord& get_last(RangeAndString& r) { return std::get<0>(r).last; }
   1509 
   1510 bool option_element_compare(RangeAndString const& lhs, RangeAndString const& rhs)
   1511 {
   1512     return std::get<0>(lhs).first == std::get<0>(rhs).first ?
   1513         std::get<0>(lhs).last < std::get<0>(rhs).last
   1514       : std::get<0>(lhs).first < std::get<0>(rhs).first;
   1515 }
   1516 
   1517 void option_list_postprocess(Vector<RangeAndString, MemoryDomain::Options>& opt)
   1518 {
   1519     std::sort(opt.begin(), opt.end(), option_element_compare);
   1520 }
   1521 
   1522 void option_update(RangeAndStringList& opt, const Context& context)
   1523 {
   1524     update_ranges(context.buffer(), opt.prefix, opt.list);
   1525     opt.prefix = context.buffer().timestamp();
   1526 }
   1527 
   1528 bool option_add_from_strings(Vector<RangeAndString, MemoryDomain::Options>& opt, ConstArrayView<String> strs)
   1529 {
   1530     auto vec = option_from_strings(Meta::Type<Vector<RangeAndString, MemoryDomain::Options>>{}, strs);
   1531     if (vec.empty())
   1532         return false;
   1533     auto middle = opt.insert(opt.end(),
   1534                              std::make_move_iterator(vec.begin()),
   1535                              std::make_move_iterator(vec.end()));
   1536     std::sort(middle, opt.end(), option_element_compare);
   1537     std::inplace_merge(opt.begin(), middle, opt.end(), option_element_compare);
   1538     return true;
   1539 }
   1540 
   1541 const HighlighterDesc ranges_desc = {
   1542     "Parameters: <option name>\n"
   1543     "Use the range-specs option given as parameter to highlight buffer\n"
   1544     "each spec is interpreted as a face to apply to the range",
   1545     {}
   1546 };
   1547 struct RangesHighlighter : OptionBasedHighlighter<RangeAndStringList, RangesHighlighter>
   1548 {
   1549     using RangesHighlighter::OptionBasedHighlighter::OptionBasedHighlighter;
   1550 private:
   1551     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
   1552     {
   1553         auto& buffer = context.context.buffer();
   1554         auto& range_and_faces = get_option(context);
   1555         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
   1556         range_and_faces.prefix = buffer.timestamp();
   1557 
   1558         for (auto& [range, face] : range_and_faces.list)
   1559         {
   1560             try
   1561             {
   1562                 if (buffer.is_valid(range.first) and (buffer.is_valid(range.last) and not buffer.is_end(range.last)))
   1563                     highlight_range(display_buffer, range.first, buffer.char_next(range.last), false,
   1564                                     apply_face(context.context.faces()[face]));
   1565             }
   1566             catch (runtime_error&)
   1567             {}
   1568         }
   1569     }
   1570 };
   1571 
   1572 const HighlighterDesc replace_ranges_desc = {
   1573     "Parameters: <option name>\n"
   1574     "Use the range-specs option given as parameter to highlight buffer\n"
   1575     "each spec is interpreted as a display line to display in place of the range",
   1576     {}
   1577 };
   1578 struct ReplaceRangesHighlighter : OptionBasedHighlighter<RangeAndStringList, ReplaceRangesHighlighter, HighlightPass::Replace>
   1579 {
   1580     using ReplaceRangesHighlighter::OptionBasedHighlighter::OptionBasedHighlighter;
   1581 private:
   1582     static bool is_valid(Buffer& buffer, BufferCoord c)
   1583     {
   1584         return c.line >= 0 and c.column >= 0 and c.line < buffer.line_count() and c.column <= buffer[c.line].length();
   1585     }
   1586 
   1587     static bool is_fully_selected(const SelectionList& sels, const InclusiveBufferRange& range)
   1588     {
   1589         auto it = std::lower_bound(sels.begin(), sels.end(), range.first, [](const Selection& s, const BufferCoord& c) { return s.max() < c; });
   1590         if (it == sels.end())
   1591             return true;
   1592         return it->min() > range.last or (it->min() <= range.first and it->max() >= range.last);
   1593     }
   1594 
   1595     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange) override
   1596     {
   1597         auto& buffer = context.context.buffer();
   1598         auto& sels = context.context.selections();
   1599         auto& range_and_faces = get_option(context);
   1600         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
   1601         range_and_faces.prefix = buffer.timestamp();
   1602 
   1603         for (auto& [range, spec] : range_and_faces.list)
   1604         {
   1605             try
   1606             {
   1607                 if (not is_valid(buffer, range.first) or (not is_empty(range) and not is_valid(buffer, range.last)) or not is_fully_selected(sels, range))
   1608                     continue;
   1609                 auto end = is_empty(range) ? range.first : buffer.char_next(range.last);
   1610                 replace_range(display_buffer, range.first, end,
   1611                               [&, range=BufferRange{range.first, end}]
   1612                               (DisplayLineList& lines, DisplayLineList::iterator line, DisplayLine::iterator pos){
   1613                                   auto it = spec.begin(), eol = find(spec, '\n');
   1614                                   while (true)
   1615                                   {
   1616                                       for (auto& atom : parse_display_line({it, eol}, context.context.faces()))
   1617                                       {
   1618                                           atom.replace(range);
   1619                                           pos = ++line->insert(pos, std::move(atom));
   1620                                       }
   1621                                       if (eol == spec.end())
   1622                                           break;
   1623                                       auto remaining = line->extract(pos, line->end());
   1624                                       line = lines.insert(++line, remaining);
   1625                                       pos = line->begin();
   1626                                       it = ++eol;
   1627                                       eol = std::find(it, spec.end(), '\n');
   1628                                   }
   1629                               });
   1630             }
   1631             catch (runtime_error&)
   1632             {}
   1633         }
   1634     }
   1635 
   1636     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
   1637     {
   1638         auto& buffer = context.context.buffer();
   1639         auto& sels = context.context.selections();
   1640         auto& range_and_faces = get_option(context);
   1641         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
   1642         range_and_faces.prefix = buffer.timestamp();
   1643 
   1644         for (auto& [range, spec] : range_and_faces.list)
   1645         {
   1646             if (not is_valid(buffer, range.first) or (not is_empty(range) and not is_valid(buffer, range.last)) or not is_fully_selected(sels, range))
   1647                 continue;
   1648 
   1649             auto last = is_empty(range) ? range.first : buffer.char_next(range.last);
   1650             if (range.first.line < setup.first_line and last.line >= setup.first_line)
   1651                 setup.first_line = range.first.line;
   1652 
   1653             if (last.line >= setup.first_line and
   1654                 range.first.line <= setup.first_line + setup.line_count and
   1655                 range.first.line != last.line)
   1656             {
   1657                 auto added_count = std::count(spec.begin(), spec.end(), '\n');
   1658                 auto removed_count = last.line - range.first.line;
   1659                 setup.line_count += removed_count - added_count;
   1660             }
   1661         }
   1662     }
   1663 };
   1664 
   1665 HighlightPass parse_passes(StringView str)
   1666 {
   1667     HighlightPass passes{};
   1668     for (auto pass : str | split<StringView>('|'))
   1669     {
   1670         if (pass == "colorize")
   1671             passes |= HighlightPass::Colorize;
   1672         else if (pass == "move")
   1673             passes |= HighlightPass::Move;
   1674         else if (pass == "wrap")
   1675             passes |= HighlightPass::Wrap;
   1676         else if (pass == "replace")
   1677             passes |= HighlightPass::Replace;
   1678         else
   1679             throw runtime_error{format("invalid highlight pass: {}", pass)};
   1680     }
   1681     if (passes == HighlightPass{})
   1682         throw runtime_error{"no passes specified"};
   1683 
   1684     return passes;
   1685 }
   1686 
   1687 const HighlighterDesc higlighter_group_desc = {
   1688     "Parameters: [-passes <passes>]\n"
   1689     "Creates a group that can contain other highlighters",
   1690     { {
   1691         { "passes", { ArgCompleter{}, "flags(colorize|move|wrap|replace) "
   1692                                        "kind of highlighters can be put in the group "
   1693                                        "(default colorize)" } } },
   1694         ParameterDesc::Flags::SwitchesOnlyAtStart, 0, 0
   1695     }
   1696 };
   1697 UniquePtr<Highlighter> create_highlighter_group(HighlighterParameters params, Highlighter*)
   1698 {
   1699     ParametersParser parser{params, higlighter_group_desc.params};
   1700     HighlightPass passes = parse_passes(parser.get_switch("passes").value_or("colorize"));
   1701 
   1702     return make_unique_ptr<HighlighterGroup>(passes);
   1703 }
   1704 
   1705 const HighlighterDesc ref_desc = {
   1706     "Parameters: [-passes <passes>] <path>\n"
   1707     "Reference the highlighter at <path> in shared highlighters",
   1708     { {
   1709         { "passes", { ArgCompleter{}, "flags(colorize|move|wrap|replace) "
   1710                                       "kind of highlighters that can be referenced "
   1711                                       "(default colorize)" } } },
   1712         ParameterDesc::Flags::SwitchesOnlyAtStart, 1, 1
   1713     }
   1714 };
   1715 struct ReferenceHighlighter : Highlighter
   1716 {
   1717     ReferenceHighlighter(HighlightPass passes, String name)
   1718         : Highlighter{passes}, m_name{std::move(name)} {}
   1719 
   1720     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
   1721     {
   1722         ParametersParser parser{params, ref_desc.params};
   1723         HighlightPass passes = parse_passes(parser.get_switch("passes").value_or("colorize"));
   1724         return make_unique_ptr<ReferenceHighlighter>(passes, parser[0]);
   1725     }
   1726 
   1727 private:
   1728     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
   1729     {
   1730         static Vector<std::pair<StringView, BufferRange>> running_refs;
   1731         const std::pair<StringView, BufferRange> desc{m_name, range};
   1732         if (contains(running_refs, desc))
   1733             return write_to_debug_buffer(format("highlighting recursion detected with ref to {}", m_name));
   1734 
   1735         running_refs.push_back(desc);
   1736         auto pop_desc = OnScopeEnd([] { running_refs.pop_back(); });
   1737 
   1738         try
   1739         {
   1740             SharedHighlighters::instance().get_child(m_name).highlight(context, display_buffer, range);
   1741         }
   1742         catch (child_not_found&)
   1743         {}
   1744     }
   1745 
   1746     void do_compute_display_setup(HighlightContext context, DisplaySetup& setup) const override
   1747     {
   1748         try
   1749         {
   1750             SharedHighlighters::instance().get_child(m_name).compute_display_setup(context, setup);
   1751         }
   1752         catch (child_not_found&)
   1753         {}
   1754     }
   1755 
   1756     const String m_name;
   1757 };
   1758 
   1759 struct RegexMatch
   1760 {
   1761     LineCount line;
   1762     ByteCount begin;
   1763     ByteCount end;
   1764     uint16_t capture_pos;
   1765     uint16_t capture_len;
   1766 
   1767     BufferCoord begin_coord() const { return { line, begin }; }
   1768     BufferCoord end_coord() const { return { line, end }; }
   1769     bool empty() const { return begin == end; }
   1770 
   1771     StringView capture(const Buffer& buffer) const
   1772     {
   1773         if (capture_len == 0)
   1774             return {};
   1775         return buffer[line].substr(begin + capture_pos, ByteCount{capture_len});
   1776     }
   1777 };
   1778 
   1779 using RegexMatchList = Vector<RegexMatch, MemoryDomain::Regions>;
   1780 
   1781 struct RegionMatches : UseMemoryDomain<MemoryDomain::Highlight>
   1782 {
   1783     RegexMatchList begin_matches;
   1784     RegexMatchList end_matches;
   1785     RegexMatchList recurse_matches;
   1786 };
   1787 
   1788 struct ForwardHighlighterApplier
   1789 {
   1790     DisplayBuffer& display_buffer;
   1791     HighlightContext& context;
   1792     DisplayLineList::iterator cur_line = display_buffer.lines().begin();
   1793     DisplayLineList::iterator end_line = display_buffer.lines().end();
   1794     DisplayLine::iterator cur_atom = cur_line->begin();
   1795     DisplayBuffer region_display{};
   1796 
   1797     void operator()(BufferCoord begin, BufferCoord end, Highlighter& highlighter)
   1798     {
   1799         if (begin == end)
   1800             return;
   1801 
   1802         auto first_line = std::find_if(cur_line, end_line, [&](auto&& line) { return line.range().end > begin; });
   1803         if (first_line != cur_line and first_line != end_line)
   1804             cur_atom = first_line->begin();
   1805         cur_line = first_line;
   1806         if (cur_line == end_line or cur_line->range().begin >= end)
   1807             return;
   1808 
   1809         auto& region_lines = region_display.lines();
   1810         region_lines.clear();
   1811         Vector<std::pair<DisplayLineList::iterator, size_t>> insert_pos;
   1812         while (cur_line != end_line and cur_line->range().begin < end)
   1813         {
   1814             auto& line = *cur_line;
   1815             auto first = std::find_if(cur_atom, line.end(), [&](auto&& atom) { return atom.has_buffer_range() and atom.end() > begin; });
   1816             if (first != line.end() and first->type() == DisplayAtom::Range and first->begin() < begin)
   1817                 first = ++line.split(first, begin);
   1818             auto idx = first - line.begin();
   1819 
   1820             auto last = std::find_if(first, line.end(), [&](auto&& atom) { return atom.has_buffer_range() and atom.end() > end; });
   1821             if (last != line.end() and last->type() == DisplayAtom::Range and last->begin() < end)
   1822                 last = ++line.split(last, end);
   1823 
   1824             if (line.begin() + idx != last)
   1825             {
   1826                 insert_pos.emplace_back(cur_line, idx);
   1827                 region_lines.push_back(line.extract(line.begin() + idx, last));
   1828             }
   1829 
   1830             if (idx != line.atoms().size())
   1831                 break;
   1832             else if (++cur_line != end_line)
   1833                 cur_atom = cur_line->begin();
   1834         }
   1835 
   1836         if (region_lines.empty())
   1837             return;
   1838 
   1839         region_display.compute_range();
   1840         highlighter.highlight(context, region_display, {begin, end});
   1841 
   1842         for (size_t i = 0; i < insert_pos.size(); ++i)
   1843         {
   1844             auto& [line_it, idx] = insert_pos[i];
   1845             auto& atoms = region_lines[i].atoms();
   1846             auto it = line_it->insert(
   1847                 line_it->begin() + idx,
   1848                 std::move_iterator(atoms.begin()),
   1849                 std::move_iterator(atoms.end()));
   1850 
   1851             if (line_it == cur_line)
   1852                 cur_atom = it + atoms.size();
   1853         }
   1854     }
   1855 };
   1856 
   1857 const HighlighterDesc default_region_desc = {
   1858     "Parameters: <delegate_type> <delegate_params>...\n"
   1859     "Define the default region of a regions highlighter",
   1860     {}
   1861 };
   1862 const HighlighterDesc region_desc = {
   1863     "Parameters:  [-match-capture] [-recurse <recurse>] <opening> <closing> <type> <params>...\n"
   1864     "Define a region for a regions highlighter, and apply the given delegate\n"
   1865     "highlighter as defined by <type> and eventual <params>...\n"
   1866     "The region starts at <begin> match and ends at the first <end>",
   1867     { {
   1868         { "match-capture", { {}, "only consider region ending/recurse delimiters whose first capture group match the region beginning delimiter" } },
   1869         { "recurse",       { ArgCompleter{}, "make the region end on the first ending delimiter that does not close the given parameter" } } },
   1870         ParameterDesc::Flags::SwitchesOnlyAtStart | ParameterDesc::Flags::IgnoreUnknownSwitches,
   1871         3
   1872     }
   1873 };
   1874 const HighlighterDesc regions_desc = {
   1875     "Holds child region highlighters and segments the buffer in ranges based on those regions\n"
   1876     "definitions. The regions highlighter finds the next region to start by finding which\n"
   1877     "of its child region has the leftmost starting point from current position. In between\n"
   1878     "regions, the default-region child highlighter is applied (if such a child exists)",
   1879     {}
   1880 };
   1881 struct RegionsHighlighter : public Highlighter
   1882 {
   1883 public:
   1884     RegionsHighlighter()
   1885         : Highlighter{HighlightPass::Colorize} {}
   1886 
   1887     void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
   1888     {
   1889         if (m_regions.empty())
   1890             return;
   1891 
   1892         auto display_range = display_buffer.range();
   1893         const auto& buffer = context.context.buffer();
   1894         auto& regions = get_regions_for_range(buffer, range);
   1895 
   1896         auto begin = std::lower_bound(regions.begin(), regions.end(), display_range.begin,
   1897                                       [](const Region& r, BufferCoord c) { return r.end < c; });
   1898         auto end = std::lower_bound(begin, regions.end(), display_range.end,
   1899                                     [](const Region& r, BufferCoord c) { return r.begin < c; });
   1900         auto correct = [&](BufferCoord c) -> BufferCoord {
   1901             if (not buffer.is_end(c) and buffer[c.line].length() == c.column)
   1902                 return {c.line+1, 0};
   1903             return c;
   1904         };
   1905 
   1906         auto default_region_it = m_regions.find(m_default_region);
   1907         const bool apply_default = default_region_it != m_regions.end();
   1908 
   1909         auto last_begin = (begin == regions.begin()) ? range.begin : (begin-1)->end;
   1910         kak_assert(begin <= end);
   1911 
   1912         ForwardHighlighterApplier apply_highlighter{display_buffer, context};
   1913         for (; begin != end; ++begin)
   1914         {
   1915             if (apply_default and last_begin < begin->begin)
   1916                 apply_highlighter(correct(last_begin), correct(begin->begin), *default_region_it->value);
   1917 
   1918             apply_highlighter(correct(begin->begin), correct(begin->end), *begin->highlighter);
   1919             last_begin = begin->end;
   1920         }
   1921         if (apply_default and last_begin < display_range.end)
   1922             apply_highlighter(correct(last_begin), range.end, *default_region_it->value);
   1923 
   1924         display_buffer.compute_range();
   1925     }
   1926 
   1927     bool has_children() const override { return true; }
   1928 
   1929     Highlighter& get_child(StringView path) override
   1930     {
   1931         auto sep_it = find(path, '/');
   1932         StringView id(path.begin(), sep_it);
   1933         auto it = m_regions.find(id);
   1934         if (it == m_regions.end())
   1935             throw child_not_found(format("no such id: {}", id));
   1936         if (sep_it == path.end())
   1937             return *it->value;
   1938         else
   1939             return it->value->get_child({sep_it+1, path.end()});
   1940     }
   1941 
   1942     void add_child(String name, UniquePtr<Highlighter>&& hl, bool override) override
   1943     {
   1944         if (not dynamic_cast<RegionHighlighter*>(hl.get()))
   1945             throw runtime_error{"only region highlighter can be added as child of a regions highlighter"};
   1946         auto it = m_regions.find(name);
   1947         if (not override and it != m_regions.end())
   1948             throw runtime_error{format("duplicate id: '{}'", name)};
   1949 
   1950         UniquePtr<RegionHighlighter> region_hl{dynamic_cast<RegionHighlighter*>(hl.release())};
   1951         if (region_hl->is_default())
   1952         {
   1953             if (not m_default_region.empty())
   1954                 throw runtime_error{"default region already defined"};
   1955             m_default_region = name;
   1956         }
   1957 
   1958         if (it != m_regions.end())
   1959             it->value = std::move(region_hl);
   1960         else
   1961             m_regions.insert({std::move(name), std::move(region_hl)});
   1962         ++m_regions_timestamp;
   1963     }
   1964 
   1965     void remove_child(StringView id) override
   1966     {
   1967         if (id == m_default_region)
   1968             m_default_region = String{};
   1969 
   1970         auto it = m_regions.find(id);
   1971         if (it == m_regions.end())
   1972             throw child_not_found(format("no such id: {}", id));
   1973         m_regions.remove(it);
   1974         ++m_regions_timestamp;
   1975     }
   1976 
   1977     Completions complete_child(StringView path, ByteCount cursor_pos, bool group) const override
   1978     {
   1979         auto sep_it = find(path, '/');
   1980         if (sep_it != path.end())
   1981         {
   1982             ByteCount offset = sep_it+1 - path.begin();
   1983             Highlighter& hl = const_cast<RegionsHighlighter*>(this)->get_child({path.begin(), sep_it});
   1984             return offset_pos(hl.complete_child(path.substr(offset), cursor_pos - offset, group), offset);
   1985         }
   1986 
   1987         auto container = m_regions | transform(&decltype(m_regions)::Item::key);
   1988         auto completions_flags = group ? Completions::Flags::None : Completions::Flags::Menu;
   1989         return { 0, 0, complete(path, cursor_pos, container), completions_flags };
   1990     }
   1991 
   1992     static UniquePtr<Highlighter> create(HighlighterParameters params, Highlighter*)
   1993     {
   1994         if (not params.empty())
   1995             throw runtime_error{"unexpected parameters"};
   1996         return make_unique_ptr<RegionsHighlighter>();
   1997     }
   1998 
   1999     static bool is_regions(Highlighter* parent)
   2000     {
   2001         if (dynamic_cast<RegionsHighlighter*>(parent))
   2002             return true;
   2003         if (auto* region = dynamic_cast<RegionHighlighter*>(parent))
   2004             return is_regions(&region->delegate());
   2005         return false;
   2006     }
   2007 
   2008     static UniquePtr<Highlighter> create_region(HighlighterParameters params, Highlighter* parent)
   2009     {
   2010         if (not is_regions(parent))
   2011             throw runtime_error{"region highlighter can only be added to a regions parent"};
   2012 
   2013         ParametersParser parser{params, region_desc.params};
   2014 
   2015         const bool match_capture = (bool)parser.get_switch("match-capture");
   2016         if (parser[0].empty() or parser[1].empty())
   2017             throw runtime_error("begin and end must not be empty");
   2018 
   2019         const auto& type = parser[2];
   2020         auto& registry = HighlighterRegistry::instance();
   2021         auto it = registry.find(type);
   2022         if (it == registry.end())
   2023             throw runtime_error(format("no such highlighter type: '{}'", type));
   2024 
   2025         // validate regexes, TODO: less costly
   2026         Regex{parser[0]};
   2027         Regex{parser[1]};
   2028         if (auto recurse_switch = parser.get_switch("recurse"))
   2029             Regex{*recurse_switch};
   2030 
   2031         auto delegate = it->value.factory(parser.positionals_from(3), nullptr);
   2032         return make_unique_ptr<RegionHighlighter>(std::move(delegate), parser[0], parser[1], parser.get_switch("recurse").value_or("").str(), match_capture);
   2033     }
   2034 
   2035     static UniquePtr<Highlighter> create_default_region(HighlighterParameters params, Highlighter* parent)
   2036     {
   2037         if (not is_regions(parent))
   2038             throw runtime_error{"default-region highlighter can only be added to a regions parent"};
   2039 
   2040         static const ParameterDesc param_desc{ {}, ParameterDesc::Flags::SwitchesOnlyAtStart, 1 };
   2041         ParametersParser parser{params, param_desc};
   2042 
   2043         const auto& type = parser[0];
   2044         auto& registry = HighlighterRegistry::instance();
   2045         auto it = registry.find(type);
   2046         if (it == registry.end())
   2047             throw runtime_error(format("no such highlighter type: '{}'", type));
   2048 
   2049         auto delegate = it->value.factory(parser.positionals_from(1), nullptr);
   2050         return make_unique_ptr<RegionHighlighter>(std::move(delegate));
   2051     }
   2052 
   2053 private:
   2054     struct RegionHighlighter : public Highlighter
   2055     {
   2056         RegionHighlighter(UniquePtr<Highlighter>&& delegate,
   2057                           String begin, String end, String recurse,
   2058                           bool match_capture)
   2059             : Highlighter{delegate->passes()},
   2060               m_delegate{std::move(delegate)},
   2061               m_begin{std::move(begin)}, m_end{std::move(end)}, m_recurse{std::move(recurse)},
   2062               m_match_capture{match_capture}
   2063        {
   2064        }
   2065 
   2066         RegionHighlighter(UniquePtr<Highlighter>&& delegate)
   2067             : Highlighter{delegate->passes()}, m_delegate{std::move(delegate)}, m_default{true}
   2068        {
   2069        }
   2070 
   2071         bool has_children() const override
   2072         {
   2073             return m_delegate->has_children();
   2074         }
   2075 
   2076         Highlighter& get_child(StringView path) override
   2077         {
   2078             return m_delegate->get_child(path);
   2079         }
   2080 
   2081         void add_child(String name, UniquePtr<Highlighter>&& hl, bool override) override
   2082         {
   2083             return m_delegate->add_child(name, std::move(hl), override);
   2084         }
   2085 
   2086         void remove_child(StringView id) override
   2087         {
   2088             return m_delegate->remove_child(id);
   2089         }
   2090 
   2091         Completions complete_child(StringView path, ByteCount cursor_pos, bool group) const override
   2092         {
   2093             return m_delegate->complete_child(path, cursor_pos, group);
   2094         }
   2095 
   2096         void fill_unique_ids(Vector<StringView>& unique_ids) const override
   2097         {
   2098             return m_delegate->fill_unique_ids(unique_ids);
   2099         }
   2100 
   2101         void do_highlight(HighlightContext context, DisplayBuffer& display_buffer, BufferRange range) override
   2102         {
   2103             return m_delegate->highlight(context, display_buffer, range);
   2104         }
   2105 
   2106 
   2107         bool match_capture() const { return m_match_capture; }
   2108         bool is_default() const { return m_default; }
   2109 
   2110         Highlighter& delegate() { return *m_delegate; }
   2111 
   2112     // private:
   2113         UniquePtr<Highlighter> m_delegate;
   2114 
   2115         String m_begin;
   2116         String m_end;
   2117         String m_recurse;
   2118         bool  m_match_capture = false;
   2119         bool  m_default = false;
   2120     };
   2121 
   2122     struct Region
   2123     {
   2124         BufferCoord begin;
   2125         BufferCoord end;
   2126         RegionHighlighter* highlighter;
   2127     };
   2128     using RegionList = Vector<Region, MemoryDomain::Highlight>;
   2129 
   2130     struct RegexKey
   2131     {
   2132         StringView regex;
   2133         bool match_captures;
   2134 
   2135         friend size_t hash_value(const RegexKey& key) { return hash_values(key.regex, key.match_captures); }
   2136         friend bool operator==(const RegexKey&, const RegexKey&) = default;
   2137     };
   2138 
   2139     struct Cache
   2140     {
   2141         size_t buffer_timestamp = 0;
   2142         size_t regions_timestamp = 0;
   2143         LineRangeSet ranges;
   2144         HashMap<RegexKey, RegexMatchList> matches;
   2145         HashMap<BufferRange, RegionList, MemoryDomain::Highlight> regions;
   2146     };
   2147 
   2148 
   2149     using RegionAndMatch = std::pair<size_t, RegexMatchList::const_iterator>;
   2150 
   2151     static bool compare_to_begin(const RegexMatch& lhs, BufferCoord rhs)
   2152     {
   2153         return lhs.begin_coord() < rhs;
   2154     }
   2155 
   2156     RegexMatchList::const_iterator find_matching_end(const Buffer& buffer, BufferCoord beg_pos, const RegexMatchList& end_matches, const RegexMatchList& recurse_matches, Optional<StringView> capture) const
   2157     {
   2158         auto end_it = end_matches.begin();
   2159         auto rec_it = recurse_matches.begin();
   2160         int recurse_level = 0;
   2161         while (true)
   2162         {
   2163             end_it = std::lower_bound(end_it, end_matches.end(), beg_pos,
   2164                                       compare_to_begin);
   2165             rec_it = std::lower_bound(rec_it, recurse_matches.end(), beg_pos,
   2166                                       compare_to_begin);
   2167 
   2168             if (end_it == end_matches.end())
   2169                 return end_it;
   2170 
   2171             while (rec_it != recurse_matches.end() and
   2172                    rec_it->end_coord() <= end_it->end_coord())
   2173             {
   2174                 if (not capture or rec_it->capture(buffer) == *capture)
   2175                     ++recurse_level;
   2176                 ++rec_it;
   2177             }
   2178 
   2179             if (not capture or *capture == end_it->capture(buffer))
   2180             {
   2181                 if (recurse_level == 0)
   2182                     return end_it;
   2183                 --recurse_level;
   2184             }
   2185 
   2186             if (beg_pos != end_it->end_coord())
   2187                 beg_pos = end_it->end_coord();
   2188             ++end_it;
   2189         }
   2190     }
   2191 
   2192     // find the begin closest to pos in all matches
   2193     Optional<RegionAndMatch> find_next_begin(const Cache& cache, BufferCoord pos) const
   2194     {
   2195         Optional<RegionAndMatch> res;
   2196 
   2197         for (size_t i = 0; i < m_regions.size(); ++i)
   2198         {
   2199             const auto& [key, region] = m_regions.item(i);
   2200             if (region->is_default())
   2201                 continue;
   2202 
   2203             const auto& matches = cache.matches.get(RegexKey{region->m_begin, region->match_capture()});
   2204             auto it = std::lower_bound(matches.begin(), matches.end(), pos, compare_to_begin);
   2205             if (it != matches.end() and (not res or it->begin_coord() < res->second->begin_coord()))
   2206                 res = RegionAndMatch{i, it};
   2207         }
   2208         return res;
   2209     }
   2210 
   2211     void add_regex(const String& str, bool captures)
   2212     {
   2213         const RegexKey key{str, captures};
   2214         if (str.empty() or m_regexes.contains(key))
   2215             return;
   2216 
   2217         auto flags = RegexCompileFlags::Optimize;
   2218         if (not captures)
   2219             flags |= RegexCompileFlags::NoSubs;
   2220 
   2221         m_regexes.insert({key, Regex{str, flags}});
   2222     }
   2223 
   2224     class MatchAdder
   2225     {
   2226     public:
   2227         MatchAdder(RegionsHighlighter& region, const Buffer& buffer, Cache& cache) : m_buffer(buffer)
   2228         {
   2229             for (auto& [key, regex] : region.m_regexes)
   2230                 cache.matches[key];
   2231             for (auto& [key, regex] : region.m_regexes)
   2232                 m_matchers.push_back(Matcher{cache.matches.get(key), regex});
   2233         }
   2234 
   2235         ~MatchAdder()
   2236         {
   2237             // Move new matches into position.
   2238             for (auto& [matches, regex, pivot, vm] : m_matchers)
   2239                 std::inplace_merge(matches.begin(), matches.begin() + pivot, matches.end(),
   2240                                    [](const auto& lhs, const auto& rhs) { return lhs.line < rhs.line; });
   2241         }
   2242 
   2243         void add(LineRange range)
   2244         {
   2245             for (auto line = range.begin; line < range.end; ++line)
   2246             {
   2247                 const StringView l = m_buffer[line];
   2248                 const auto flags = RegexExecFlags::NotEndOfLine; // buffer line already ends with \n
   2249 
   2250                 for (auto& [matches, regex, pivot, vm] : m_matchers)
   2251                 {
   2252                     auto extra_flags = RegexExecFlags::None;
   2253                     auto pos = l.begin();
   2254                     while (vm.exec(pos, l.end(), l.begin(), l.end(), flags | extra_flags))
   2255                     {
   2256                         ConstArrayView<const char*> captures = vm.captures();
   2257                         const bool with_capture = regex.mark_count() > 0 and captures[2] != nullptr and
   2258                                                   captures[1] - captures[0] < std::numeric_limits<uint16_t>::max();
   2259                         matches.push_back({
   2260                             line,
   2261                             (int)(captures[0] - l.begin()),
   2262                             (int)(captures[1] - l.begin()),
   2263                             (uint16_t)(with_capture ? captures[2] - captures[0] : 0),
   2264                             (uint16_t)(with_capture ? captures[3] - captures[2] : 0)
   2265                         });
   2266                         pos = captures[1];
   2267 
   2268                         extra_flags = (captures[0] == captures[1]) ? RegexExecFlags::NotInitialNull : RegexExecFlags::None;
   2269                     }
   2270                 }
   2271             }
   2272         }
   2273 
   2274     private:
   2275         struct Matcher
   2276         {
   2277             RegexMatchList& matches;
   2278             const Regex& regex;
   2279             size_t pivot = matches.size();
   2280             ThreadedRegexVM<const char*, RegexMode::Forward | RegexMode::Search> vm{*regex.impl()};
   2281         };
   2282 
   2283         const Buffer& m_buffer;
   2284         Vector<Matcher> m_matchers;
   2285     };
   2286 
   2287     void update_changed_lines(const Buffer& buffer, ConstArrayView<LineModification> modifs, Cache& cache)
   2288     {
   2289         for (auto& [key, matches] : cache.matches)
   2290         {
   2291             // remove out of date matches and update line for others
   2292             auto ins_pos = matches.begin();
   2293             for (auto it = ins_pos; it != matches.end(); ++it)
   2294             {
   2295                 auto modif_it = std::upper_bound(modifs.begin(), modifs.end(), it->line,
   2296                                                  [](const LineCount& l, const LineModification& c)
   2297                                                  { return l < c.old_line; });
   2298 
   2299                 if (modif_it != modifs.begin())
   2300                 {
   2301                     auto& prev = *(modif_it-1);
   2302                     if (it->line < prev.old_line + prev.num_removed)
   2303                         continue; // match removed
   2304 
   2305                     it->line += prev.diff();
   2306                 }
   2307 
   2308                 kak_assert(buffer.is_valid(it->begin_coord()) or
   2309                            buffer[it->line].length() == it->begin);
   2310                 kak_assert(buffer.is_valid(it->end_coord()) or
   2311                            buffer[it->line].length() == it->end);
   2312 
   2313                 if (ins_pos != it)
   2314                     *ins_pos = std::move(*it);
   2315                 ++ins_pos;
   2316             }
   2317             matches.erase(ins_pos, matches.end());
   2318         }
   2319     }
   2320 
   2321     bool update_matches(Cache& cache, const Buffer& buffer, LineRange range)
   2322     {
   2323         const size_t buffer_timestamp = buffer.timestamp();
   2324         if (cache.buffer_timestamp == 0 or
   2325             cache.regions_timestamp != m_regions_timestamp)
   2326         {
   2327             m_regexes.clear();
   2328             cache.matches.clear();
   2329             for (auto& [key, region] : m_regions)
   2330             {
   2331                 add_regex(region->m_begin, region->match_capture());
   2332                 add_regex(region->m_end, region->match_capture());
   2333                 add_regex(region->m_recurse, region->match_capture());
   2334             }
   2335 
   2336             MatchAdder{*this, buffer, cache}.add(range);
   2337             cache.ranges.reset(range);
   2338             cache.buffer_timestamp = buffer_timestamp;
   2339             cache.regions_timestamp = m_regions_timestamp;
   2340             return true;
   2341         }
   2342         else
   2343         {
   2344             bool modified = false;
   2345             if (cache.buffer_timestamp != buffer_timestamp)
   2346             {
   2347                 auto modifs = compute_line_modifications(buffer, cache.buffer_timestamp);
   2348                 update_changed_lines(buffer, modifs, cache);
   2349                 cache.ranges.update(modifs);
   2350                 cache.buffer_timestamp = buffer_timestamp;
   2351                 modified = true;
   2352             }
   2353 
   2354             MatchAdder matches{*this, buffer, cache};
   2355             cache.ranges.add_range(range, [&](const LineRange& range) {
   2356                 if (range.begin == range.end)
   2357                     return;
   2358                 matches.add(range);
   2359                 modified = true;
   2360             });
   2361             return modified;
   2362         }
   2363     }
   2364 
   2365     const RegionList& get_regions_for_range(const Buffer& buffer, BufferRange range)
   2366     {
   2367         Cache& cache = m_cache.get(buffer);
   2368         if (update_matches(cache, buffer, {range.begin.line, std::min(buffer.line_count(), range.end.line + 1)}))
   2369             cache.regions.clear();
   2370 
   2371         auto it = cache.regions.find(range);
   2372         if (it != cache.regions.end())
   2373             return it->value;
   2374 
   2375         RegionList& regions = cache.regions[range];
   2376         RegexMatchList empty_matches{};
   2377 
   2378         for (auto begin = find_next_begin(cache, range.begin); begin; )
   2379         {
   2380             auto& [index, beg_it] = *begin;
   2381             auto& region = *m_regions.item(index).value;
   2382             auto& end_matches = cache.matches.get(RegexKey{region.m_end, region.match_capture()});
   2383             auto& recurse_matches = region.m_recurse.empty() ?
   2384                 empty_matches : cache.matches.get(RegexKey{region.m_recurse, region.match_capture()});
   2385 
   2386             auto end_it = find_matching_end(buffer, beg_it->end_coord(), end_matches, recurse_matches,
   2387                                             region.match_capture() ? beg_it->capture(buffer) : Optional<StringView>{});
   2388 
   2389             if (end_it == end_matches.end() or end_it->end_coord() >= range.end) // region continue past range end
   2390             {
   2391                 auto begin_coord = beg_it->begin_coord();
   2392                 if (begin_coord < range.end)
   2393                     regions.push_back({begin_coord, range.end, &region});
   2394                 break;
   2395             }
   2396 
   2397             auto end_coord = end_it->end_coord();
   2398             regions.push_back({beg_it->begin_coord(), end_coord, &region});
   2399 
   2400             // With empty begin and end matches (for example if the regexes
   2401             // are /"\K/ and /(?=")/), that case can happen, and would
   2402             // result in an infinite loop.
   2403             if (end_coord == beg_it->begin_coord())
   2404             {
   2405                 kak_assert(beg_it->empty() and end_it->empty());
   2406                 ++end_coord.column;
   2407             }
   2408             begin = find_next_begin(cache, end_coord);
   2409         }
   2410         return regions;
   2411     }
   2412 
   2413     HashMap<String, UniquePtr<RegionHighlighter>, MemoryDomain::Highlight> m_regions;
   2414     HashMap<RegexKey, Regex> m_regexes;
   2415     String m_default_region;
   2416 
   2417     size_t m_regions_timestamp = 0;
   2418     BufferSideCache<Cache> m_cache;
   2419 };
   2420 
   2421 void setup_builtin_highlighters(HighlighterGroup& group)
   2422 {
   2423     group.add_child("tabulations"_str, make_unique_ptr<TabulationHighlighter>());
   2424     group.add_child("unprintable"_str, make_highlighter(expand_unprintable));
   2425     group.add_child("selections"_str,  make_highlighter(highlight_selections));
   2426 }
   2427 
   2428 void register_highlighters()
   2429 {
   2430     HighlighterRegistry& registry = HighlighterRegistry::instance();
   2431 
   2432     registry.insert({
   2433         "column",
   2434         { create_column_highlighter, &column_desc } });
   2435     registry.insert({
   2436         "default-region",
   2437         { RegionsHighlighter::create_default_region, &default_region_desc } });
   2438     registry.insert({
   2439         "dynregex",
   2440         { create_dynamic_regex_highlighter, &dynamic_regex_desc } });
   2441     registry.insert({
   2442         "fill",
   2443         { create_fill_highlighter, &fill_desc } });
   2444     registry.insert({
   2445         "flag-lines",
   2446         { FlagLinesHighlighter::create, &flag_lines_desc } });
   2447     registry.insert({
   2448         "group",
   2449         { create_highlighter_group, &higlighter_group_desc } });
   2450     registry.insert({
   2451         "line",
   2452         { create_line_highlighter, &line_desc } });
   2453     registry.insert({
   2454         "number-lines",
   2455         { LineNumbersHighlighter::create, &line_numbers_desc } });
   2456     registry.insert({
   2457         "ranges",
   2458         { RangesHighlighter::create, &ranges_desc } });
   2459     registry.insert({
   2460         "ref",
   2461         { ReferenceHighlighter::create, &ref_desc } });
   2462     registry.insert({
   2463         "regex",
   2464         { RegexHighlighter::create, &regex_desc } });
   2465     registry.insert({
   2466         "region",
   2467         { RegionsHighlighter::create_region, &region_desc } });
   2468     registry.insert({
   2469         "regions",
   2470         { RegionsHighlighter::create, &regions_desc } });
   2471     registry.insert({
   2472         "replace-ranges",
   2473         { ReplaceRangesHighlighter::create, &replace_ranges_desc } });
   2474     registry.insert({
   2475         "show-matching",
   2476         { create_matching_char_highlighter, &show_matching_desc } });
   2477     registry.insert({
   2478         "show-whitespaces",
   2479         { ShowWhitespacesHighlighter::create, &show_whitespace_desc } });
   2480     registry.insert({
   2481         "wrap",
   2482         { WrapHighlighter::create, &wrap_desc } });
   2483 }
   2484 
   2485 }