walker.lua

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