walker.lua

   1 -- SPDX-License-Identifier: GPL-3.0-or-later
   2 -- © 2020 Georgi Kirilov
   3
   4 local M = {}
   5
   6 local function finishof(node) return node.finish end
   7 local function startof(node) return node.start end
   8
   9 function M.new(parser, eol_at, bol_at)
  10
  11         local function in_quasilist(t, range)
  12                 return t and t.d and not t.is_list and
  13                         range.start >= t.start + #t.d and range.finish <= t.finish + 1 - #parser.opposite[t.d]
  14         end
  15
  16         local function sexp_at(range, true_sexp)
  17                 local node, parent, nth = parser.tree.sexp_at(range)
  18                 if true_sexp or not in_quasilist(node, range) then
  19                         return node, parent, nth
  20                 else
  21                         return node.word_at(range), node
  22                 end
  23         end
  24
  25         local function escaped_at(range)
  26                 local node = parser.escaped.around(range)
  27                 -- TODO: distinguish between doublequoted strings, chars, line comments, and block comments
  28                 -- and use approprite offset comparisons for each
  29                 return node and range.start > node.start and range.finish <= node.finish and node
  30         end
  31
  32         local function find_before_innermost(t, range, key, pred)
  33                 if t.is_root or (t.d and t.start < range.start) then
  34                         if t.d and not t.is_list then
  35                                 local keypos = key(t)
  36                                 local start = keypos == startof(t)
  37                                 local finish = keypos == finishof(t)
  38                                 local newpos
  39                                 if finish then
  40                                         newpos = t.finish_before(range.finish)
  41                                 elseif start then
  42                                         newpos = t.start_before(range.start)
  43                                 end
  44                                 if newpos then
  45                                         local word = t.word_at({start = newpos, finish = newpos})
  46                                         if word and (not pred or pred(word)) then
  47                                                 return word
  48                                         end
  49                                 end
  50                                 return (not pred or pred(t)) and t
  51                         end
  52                         local _, nearest_n = t.before(range.start, startof)
  53                         if nearest_n then
  54                                 for n = nearest_n, 1, -1 do
  55                                         local child = t[n]
  56                                         if child.d and not child.is_empty then
  57                                                 local ret = find_before_innermost(child, range, key, pred)
  58                                                 if ret then
  59                                                         return ret
  60                                                 end
  61                                         elseif key(child) < key(range) and (not pred or pred(child, n, #t)) then
  62                                                 return child, n, #t
  63                                         end
  64                                 end
  65                         end
  66                         if not t.is_root and (not pred or pred(t)) then
  67                                 return t
  68                         end
  69                 end
  70         end
  71
  72         local function find_after_innermost(t, range, key, pred)
  73                 if t.is_root or (t.d and t.finish >= range.finish) then
  74                         if t.d and not t.is_list then
  75                                 local keypos = key(t)
  76                                 local start = keypos == startof(t)
  77                                 local finish = keypos == finishof(t)
  78                                 local newpos
  79                                 if finish then
  80                                         newpos = t.finish_after(math.max(t.start + #t.d, range.finish))
  81                                 elseif start then
  82                                         newpos = range.finish < t.start and t.start + #t.d or t.start_after(range.start)
  83                                 end
  84                                 if newpos then
  85                                         local word = t.word_at({start = newpos, finish = newpos})
  86                                         if word and (not pred or pred(word)) then
  87                                                 return word
  88                                         end
  89                                 end
  90                                 return (not pred or pred(t)) and t
  91                         end
  92                         local _, nearest_n = t.after(range.finish, finishof)
  93                         if nearest_n then
  94                                 for n = nearest_n, #t do
  95                                         local child = t[n]
  96                                         if child.d and not child.is_empty then
  97                                                 local ret = find_after_innermost(child, range, key, pred)
  98                                                 if ret then
  99                                                         return ret
 100                                                 end
 101                                         elseif key(child) >= key(range) and (not pred or pred(child, n, #t)) then
 102                                                 return child, n, #t
 103                                         end
 104                                 end
 105                         end
 106                         if not t.is_root and (not pred or pred(t)) then
 107                                 return t
 108                         end
 109                 end
 110         end
 111
 112         return {
 113
 114                 start_before = function(range, skip)
 115                         local _, parent = parser.tree.sexp_at(range)
 116                         local node = parent.before(range.start, startof, skip)
 117                         return node and startof(node)
 118                 end,
 119
 120                 start_after = function(range, skip)
 121                         local _, parent = parser.tree.sexp_at(range)
 122                         local node = parent.after(range.finish, startof, skip)
 123                         return node and startof(node)
 124                 end,
 125
 126                 finish_before = function(range, skip)
 127                         local _, parent = parser.tree.sexp_at(range)
 128                         local node = parent.before(range.start, finishof, skip)
 129                         return node and finishof(node) + 1
 130                 end,
 131
 132                 finish_after = function(range, skip)
 133                         local _, parent = parser.tree.sexp_at(range)
 134                         local node = parent.after(range.finish, finishof, skip)
 135                         return node and finishof(node) + 1
 136                 end,
 137
 138                 start_down_after = function(range, skip)
 139                         local node, parent = parser.tree.sexp_at(range)
 140                         if in_quasilist(node, range) then return end
 141                         if node and node.p then
 142                                 -- XXX: if we are past a prefix start, this will prevent skipping over its list
 143                                 range.start = node.start
 144                         end
 145                         local next_list = parent.find_after(range, function(t) return t.is_list end)
 146                         if next_list then
 147                                 local first = next_list.after(range.finish, startof, skip)
 148                                 if first then
 149                                         return first.start
 150                                 else
 151                                         return next_list.start + (next_list.p and #next_list.p or 0) + 1
 152                                 end
 153                         end
 154                 end,
 155
 156                 start_up_before = function(range)
 157                         local _, parent = sexp_at(range)
 158                         return parent.d and parent.start
 159                 end,
 160
 161                 finish_down_before = function(range, skip)
 162                         local node, parent = parser.tree.sexp_at(range)
 163                         if in_quasilist(node, range) then return end
 164                         local prev_list = parent.find_before(range, function(t) return t.is_list end)
 165                         if prev_list then
 166                                 local last = prev_list.before(range.start, finishof, skip)
 167                                 if last then
 168                                         return (last.finish or last.p and last.start + #last.p) + 1, prev_list
 169                                 else
 170                                         return prev_list.finish, prev_list
 171                                 end
 172                         end
 173                 end,
 174
 175                 finish_up_after = function(range)
 176                         local _, parent = sexp_at(range)
 177                         return parent.d and parent.finish + 1
 178                 end,
 179
 180                 indented_before = function(range)
 181                         return find_before_innermost(parser.tree, range, startof, function(t) return t.indent end)
 182                 end,
 183
 184                 start_left = function(range)
 185                         local node = find_before_innermost(parser.tree, range, startof)
 186                         return node and node.start
 187                 end,
 188
 189                 finish_right = function(range)
 190                         local node = find_after_innermost(parser.tree, range, finishof)
 191                         return node and node.finish + 1
 192                 end,
 193
 194                 start_float_before = function(range, up_empty_list)
 195                         if up_empty_list then
 196                                 local _, parent = sexp_at(range)
 197                                 if parent.is_empty then
 198                                         return parent.start, parent
 199                                 end
 200                         end
 201                         local node = find_before_innermost(parser.tree, range, startof, function(t, n, _)
 202                                 return not t.d or t.is_empty and n == 1 end)
 203                         return node and node.start, node
 204                 end,
 205
 206                 finish_float_after = function(range, up_empty_list)
 207                         if up_empty_list then
 208                                 local _, parent = sexp_at(range)
 209                                 if parent.is_empty then
 210                                         return parent.finish + 1, parent
 211                                 end
 212                         end
 213                         local node = find_after_innermost(parser.tree, range, finishof, function(t, n, max_n)
 214                                 -- XXX: max_n may not be correct at top level, due to the incremental parsing:
 215                                 return not t.d or t.is_empty and n == max_n end)
 216                         return node and node.finish + 1, node
 217                 end,
 218
 219                 start_word_after = function(t, range)
 220                         local newpos = t.start_after(range.start)
 221                         if newpos then
 222                                 local word = t.word_at({start = newpos, finish = newpos})
 223                                 return word and word.start
 224                         else
 225                                 local _, parent, n = sexp_at(range, true)
 226                                 local cur, nxt = parent[n], parent[n + 1]
 227                                 if nxt and cur.is_line_comment and nxt.is_line_comment then
 228                                         return nxt.start_after(range.start)
 229                                 end
 230                         end
 231                 end,
 232
 233                 finish_word_after = function(t, range)
 234                         local newpos = t.finish_after(math.max(t.start + #t.d, range.finish))
 235                         if newpos then
 236                                 local word = t.word_at({start = newpos, finish = newpos})
 237                                 return word and word.finish + 1
 238                         else
 239                                 local _, parent, n = sexp_at(range, true)
 240                                 local cur, nxt = parent[n], parent[n + 1]
 241                                 if nxt and cur.is_line_comment and nxt.is_line_comment then
 242                                         return nxt.finish_after(range.start)
 243                                 end
 244                         end
 245                 end,
 246
 247                 start_word_before = function(t, range)
 248                         local newpos = t.start_before(range.start)
 249                         if newpos then
 250                                 local word = t.word_at({start = newpos, finish = newpos})
 251                                 return word and word.start
 252                         else
 253                                 local _, parent, n = sexp_at(range, true)
 254                                 local cur, prev = parent[n], parent[n - 1]
 255                                 if prev and cur.is_line_comment and prev.is_line_comment then
 256                                         return prev.start_before(range.start)
 257                                 end
 258                         end
 259                 end,
 260
 261                 finish_word_before = function(t, range)
 262                         local newpos = t.finish_before(range.finish)
 263                         if newpos then
 264                                 local word = t.word_at({start = newpos, finish = newpos})
 265                                 return word and word.finish + 1
 266                         else
 267                                 local _, parent, n = sexp_at(range, true)
 268                                 local cur, prev = parent[n], parent[n - 1]
 269                                 if prev and cur.is_line_comment and prev.is_line_comment then
 270                                         return prev.finish_before(range.start)
 271                                 end
 272                         end
 273                 end,
 274
 275                 prev_start_wrapped = function(range)
 276                         local node, parent = parser.tree.sexp_at(range)
 277                         if in_quasilist(node, range) then parent = node end
 278                         local pstart = parent.start and (parent.start + (parent.p and #parent.p or 0) + #parent.d)
 279                         local bol = bol_at(range.start)
 280                         local prev_wrapped = (parent.is_list or parent.is_root) and parent.find_before(range,
 281                                 function(t) return t.start < bol and t.finish > bol end,
 282                                 function(t) return t.finish < bol
 283                         end)
 284                         local prev_start = prev_wrapped and prev_wrapped.start or bol
 285                         pstart = pstart or prev_start
 286                         return math.max(pstart, prev_start)
 287                 end,
 288
 289                 next_finish_wrapped = function(range)
 290                         local node, parent = parser.tree.sexp_at(range)
 291                         if in_quasilist(node, range) then parent = node end
 292                         local eol = eol_at(range.start)
 293                         local pfinish = parent.finish and parent.finish < eol and parent.finish + 1 - #parser.opposite[parent.d]
 294                         local next_wrapped = not pfinish and (parent.is_list or parent.is_root) and parent.find_after(range,
 295                                 function(t) return t.start < eol and t.finish > eol end,
 296                                 function(t) return t.start > eol
 297                         end)
 298                         local next_finish = pfinish or next_wrapped and next_wrapped.finish + 1
 299                         -- XXX: second return value, to be used for safe line-commenting:
 300                         local next_line_break = pfinish or next_wrapped and next_wrapped.start
 301                         return next_finish or eol, next_line_break
 302                 end,
 303
 304                 anylist_start = function(range)
 305                         local _, parent = sexp_at(range)
 306                         return parent.start and (parent.start + (parent.p and #parent.p or 0) + #parent.d)
 307                 end,
 308
 309                 anylist_finish = function(range)
 310                         local _, parent = sexp_at(range)
 311                         return parent.finish and parent.finish + 1 - #parser.opposite[parent.d]
 312                 end,
 313
 314                 wider_than = function(range)
 315                         local node, parent = parser.tree.sexp_at(range)
 316                         if not node and parent.is_root then return end
 317                         local pstart, pfinish
 318                         if in_quasilist(node, range) then
 319                                 parent = node
 320                                 node = node.word_at(range)
 321                         end
 322                         if not parent.is_root then
 323                                 pstart, pfinish = parent.start + (parent.p and #parent.p or 0) + #parent.d,
 324                                         parent.finish + 1 - #parser.opposite[parent.d]
 325                         end
 326                         local same_as_inner = range.start == pstart and range.finish == pfinish
 327                         local same_as_node = node and range.start == node.start and range.finish - 1 == node.finish
 328                         if node and not same_as_node then
 329                                 return node.start, node.finish + 1
 330                         elseif not same_as_inner then
 331                                 return pstart, pfinish
 332                         end
 333                         return parent.start, parent.finish + 1
 334                 end,
 335
 336                 -- opening: nil - bracketed list, false - anylist (including a quasilist)
 337                 list_at = function(range, opening)
 338                         local lcd = parser.opposite["\n"]
 339                         if opening and opening:match('[%' .. lcd .. '%"]') then
 340                                 local escaped = escaped_at(range)
 341                                 return escaped and escaped.d:find("^"..opening) and escaped
 342                         else
 343                                 local _, nodes = parser.tree.sexp_path(range)
 344                                 local parent
 345                                 local up = #nodes - (opening == false and in_quasilist(nodes[#nodes], range) and 0 or 1)
 346                                 repeat
 347                                         parent = nodes[up]
 348                                         up = up - 1
 349                                 until not parent or (opening == false or not opening or parent.d == opening)
 350                                 return parent
 351                         end
 352                 end,
 353
 354                 repl_line_at = function(range)
 355                         local last, nl = parser.tree.find_after(range, function(t) return t.indent end)
 356                         local first, nf
 357                         local node = parser.tree.around(range)
 358                         if last and node and not node.is_comment and last.start == node.start then
 359                                 local i = nl
 360                                 repeat
 361                                         i = i + 1
 362                                 until not parser.tree[i] or parser.tree[i].indent
 363                                 nf = nl
 364                                 nl = i - 1
 365                         else
 366                                 local i = nl or #parser.tree + 1
 367                                 repeat
 368                                         i = i - 1
 369                                 until i == 0 or parser.tree[i].indent
 370                                 nf = parser.tree[i] and not parser.tree[i].is_comment and i
 371                                 nl = nl and nl - 1 or #parser.tree
 372                         end
 373                         first, last = nf and parser.tree[nf], parser.tree[nl]
 374                         if first and last then
 375                                 return {start = first.start, finish = last.finish}
 376                         end
 377                 end,
 378
 379                 sexp_at = sexp_at,
 380                 escaped_at = escaped_at,
 381                 paragraph_at = parser.tree.around,
 382                 goto_path = parser.tree.goto_path,
 383                 sexp_path = parser.tree.sexp_path,
 384                 find_after = parser.tree.find_after,
 385                 find_before = parser.tree.find_before,
 386         }
 387 end
 388
 389 return M