lines2.love/move.lua

---- moving around the editor in terms of locations (loc)
--
-- locations within text lines look like this:
--   {mode='text', line=, pos=}
-- (pos counts in utf8 codepoints starting from 1)
--
-- locations within drawings look like this:
--   {mode='drawing', line=}
-- (drawing lines are atomic as far as the cursor is concerned)
--
-- all movements are built primarily using the following primitives, defined
-- further down:
--   - to_loc: (x, y) -> loc
--     identify the location at pixel coordinates (x,y) on screen
--     returns nil if (x,y) is not on screen
--   - to_coord: loc -> x, y
--     identify the top-left coordinate on screen of location loc
--     returns nil if loc is not on screen
--   - down: loc, dy -> loc
--     find the location at the start of a screen line dy pixels down from loc
--     returns nil if dy is taller than the screen
--     returns bottom of file if we hit it
--   - up: loc, dy -> loc
--     find the location at the start of a screen line dy pixels up from loc
--     returns nil if dy is taller than the screen
--     returns top of file if we hit it
--   - hor: loc, x -> loc
--     find the location at x=x0 on the same screen line as loc
--
-- I have tried to make these definitions as clear as possible while being fast enough.
-- My mental model for trading off performance for clarity:
--   - text is the bottleneck; my line drawings are clear and cheap no matter
--     how you go about things.
--   - any computation limited to the number of characters a screen can show
--     will be an order of magnitude faster than it needs to be to draw 30
--     frames per second.
--     So I don't mind doing up to 5 scans per interactive operation if that
--     makes the code clearer.
--   - no caching across frames; it makes the code less clear and has also
--     caused bugs.
--   - short-lived memory allocations that live within a single frame are cheap
--
-- This API was non-trivial to arrive at. It seems promising for any
-- pixel-based editor using proportional fonts. It seems independent of the
-- data structures the editor uses, whether arrays as here or ropes or gap
-- buffers, though I cheat a bit and use knowledge of the data structures
-- where it saves me a scan or two.

function Text.up(editor)
  local x, _ = edit.to_coord(editor, editor.cursor)  -- scan
  editor.cursor = edit.up(editor, editor.cursor, 1 --[[px]])  -- scan
  assert(editor.cursor)
  editor.cursor = edit.hor(editor, editor.cursor, x)  -- 0-1 scan
  assert(editor.cursor)
  maybe_snap_cursor_to_top_of_screen(editor)  -- 0-1 scan
end  -- 2-4 scans

function Text.down(editor)
  local x, _ = edit.to_coord(editor, editor.cursor)  -- scan
  local dy0 = edit.screen_line_height(editor, editor.cursor)
  editor.cursor = edit.down(editor, editor.cursor, dy0)  -- scan
  assert(editor.cursor)
  editor.cursor = edit.hor(editor, editor.cursor, x)  -- 0-1 scan
  assert(editor.cursor)
  maybe_snap_cursor_to_bottom_of_screen(editor)  -- 0-2 scans
end  -- 2-5 scans

function Text.left(editor)
  Text.left_without_scroll(editor)  -- 0-2 scans
  maybe_snap_cursor_to_top_of_screen(editor)  -- 0-1 scan
end  -- 0-3 scans


function Text.left_without_scroll(editor)
  if editor.cursor.pos and editor.cursor.pos > 1 then
    editor.cursor.pos = editor.cursor.pos-1
  elseif editor.cursor.line > 1 then
    editor.cursor = edit.up(editor, editor.cursor, 1 --[[px]])  -- scan
    assert(editor.cursor)
    editor.cursor = edit.hor(editor, editor.cursor, editor.right)  -- 0-1 scan
    assert(editor.cursor)
  end
end  -- 0-2 scans

-- without cheating
--? function Text.left_without_scroll(editor)
--?   local x, _ = edit.to_coord(editor, editor.cursor)  -- scan
--?   if x <= editor.left then  -- 0-2 scans
--?     editor.cursor = edit.up(editor, editor.cursor, 1 --[[px]])  -- scan
--?     editor.cursor = edit.hor(editor, editor.cursor, editor.right)  -- 0-1 scan
--?   else
--?     editor.cursor = edit.hor(editor, editor.cursor, x-1)  -- 0-1 scan
--?   end
--? end  -- 1-3 scans

function Text.right(editor)
  Text.right_without_scroll(editor)  -- 0-2 scans
  maybe_snap_cursor_to_bottom_of_screen(editor)  -- 0-2 scans
end  -- 0-4 scans

function Text.right_without_scroll(editor)
  if editor.cursor.pos and editor.cursor.pos <= utf8.len(editor.lines[editor.cursor.line].data) then
    editor.cursor.pos = editor.cursor.pos+1
  else
    local _, y = edit.to_coord(editor, editor.cursor)  -- scan
    local dy = edit.screen_line_height(editor, editor.cursor)
    local new_cursor = edit.down(editor, editor.cursor, dy)  -- scan
    if edit.lt(editor.cursor, new_cursor) then  -- there's further down to go
      editor.cursor = new_cursor
    end
  end
end  -- 0-3 scans

function Text.pageup(editor)
  editor.screen_top = edit.up(editor, editor.screen_top, editor.bottom - editor.top - editor.line_height) -- scan
  assert(editor.screen_top)
  editor.cursor = deepcopy(editor.screen_top)
  assert(editor.cursor)
end  -- 1 scan

function Text.pagedown(editor)
  editor.screen_top = edit.down(editor, editor.screen_top, editor.bottom - editor.top - editor.line_height)  -- scan
  assert(editor.screen_top)
  editor.cursor = deepcopy(editor.screen_top)
  assert(editor.cursor)
end  -- 1 scan

function Text.start_of_line(editor)
  if editor.cursor.mode == 'drawing' then return end
  editor.cursor.pos = 1
  maybe_snap_cursor_to_top_of_screen(editor)  -- 0-1 scan
end  -- 0-1 scan

function Text.end_of_line(editor)
  if editor.cursor.mode == 'drawing' then return end
  editor.cursor.pos = utf8.len(editor.lines[editor.cursor.line].data) + 1
  maybe_snap_cursor_to_bottom_of_screen(editor)  -- 0-1 scan
end  -- 0-1 scan

function Text.word_left(editor)
  -- skip some whitespace
  while true do
    if editor.cursor.pos == nil or editor.cursor.pos == 1 then
      break  -- line boundary is always whitespace
    end
    if Text.match(editor.lines[editor.cursor.line].data, editor.cursor.pos-1, '%S') then
      break
    end
    Text.left_without_scroll(editor)
  end
  -- skip some non-whitespace
  while true do
    Text.left_without_scroll(editor)
    if editor.cursor.pos == nil or editor.cursor.pos == 1 then
      break
    end
    assert(editor.cursor.pos > 1, 'bumped up against start of line')
    if Text.match(editor.lines[editor.cursor.line].data, editor.cursor.pos-1, '%s') then
      break
    end
  end
  maybe_snap_cursor_to_top_of_screen(editor)
end

function Text.word_right(editor)
  -- skip some whitespace
  while true do
    if editor.cursor.pos == nil or editor.cursor.pos > utf8.len(editor.lines[editor.cursor.line].data) then
      break
    end
    if Text.match(editor.lines[editor.cursor.line].data, editor.cursor.pos, '%S') then
      break
    end
    Text.right_without_scroll(editor)
  end
  while true do
    Text.right_without_scroll(editor)
    if editor.cursor.pos == nil or editor.cursor.pos > utf8.len(editor.lines[editor.cursor.line].data) then
      break
    end
    if Text.match(editor.lines[editor.cursor.line].data, editor.cursor.pos, '%s') then
      break
    end
  end
  maybe_snap_cursor_to_bottom_of_screen(editor)
end

function Text.match(s, pos, pat)
  local start_offset = Text.offset(s, pos)
  local end_offset = Text.offset(s, pos+1)
  assert(end_offset > start_offset, ('end_offset %d not > start_offset %d'):format(end_offset, start_offset))
  local curr = s:sub(start_offset, end_offset-1)
  return curr:match(pat)
end

function maybe_snap_cursor_to_top_of_screen(editor)
  if edit.lt(editor.cursor, editor.screen_top) then
    editor.screen_top = edit.hor(editor, editor.cursor, editor.left)  -- scan
    assert(editor.screen_top)
  end
end  -- 0-1 scan

function maybe_snap_cursor_to_bottom_of_screen(editor)
  local _, y = edit.to_coord(editor, editor.cursor)  -- scan
  local h = edit.screen_line_height(editor, editor.cursor)
  if y == nil or y > editor.bottom - editor.top - h then
    editor.screen_top = edit._up_whole_screen_lines(editor, editor.cursor, editor.bottom - editor.top - h)  -- scan
    assert(editor.screen_top)
  else
    -- no need to scroll
    return
  end
end  -- 1-2 scans

---- various primitives that simulate drawing on screen without actually doing so
--
-- These _do_ depend on the data structures the editor uses. But you should go
-- a long way just by reimplementing them if you ever change the data structures.

-- These are based on the output of edit.get_rect, which provides:
--  - an array of rects {x,y, dx,dy}, one for each line
--  - if it's a text line:
--    - rects for each screen line in rect[].screen_line_rects, and
--    - rects for each utf8 codepoint in rect[].screen_line_rects[].char_rects

-- return the location corresponding to a pixel
-- may return nil if:
--    the coord is above the top margin and the top line is not text
--    or the coord is below the bottom margin and the bottom line is not text
function edit.to_loc(editor, mx,my)
  if my < editor.top then
    return deepcopy(editor.screen_top)
  end
  local x, y = mx - editor.left, my - editor.top
  local rect
  for line_index,line in array.each(editor.lines, editor.screen_top.line) do
    if line_index == editor.screen_top.line then
      rect = edit.get_rect(editor, editor.screen_top)
    else
      rect = edit.get_rect(editor, {mode=line.mode, line=line_index, pos=1})
    end
    if line.mode == 'text' then
      if y < rect.dy then
        local s = find_y(rect.screen_line_rects, y)
        local char_rect = find_x(s.char_rects, x)
        assert(char_rect)
        return {mode='text', line=line_index, pos=char_rect.pos}
      else
        y = y - rect.dy
        if y <= 0 then
          break
        end
      end
    else
      if y < rect.dy then
        return {mode='drawing', line=line_index}
      end
      y = y - rect.dy
    end
    if y <= 0 then
      break
    end
  end
  -- below all lines; return final rect on screen
  if rect.screen_line_rects then
    local s = rect.screen_line_rects
    local c = s[#s].char_rects
    return {mode='text', line=rect.line_index, pos=c[#c].pos}
  else
    return {mode='drawing', line=rect.line_index}
  end
end

function edit.to_coord(editor, loc)  -- scans
  if edit.lt(loc, editor.screen_top) then return end
  local y = editor.top
  for line_index, line in array.each(editor.lines, editor.screen_top.line) do
    local rect
    if line_index == editor.screen_top.line then
      rect = edit.get_rect(editor, editor.screen_top)
    else
      rect = edit.get_rect(editor, {mode=line.mode, line=line_index, pos=1})
    end
    if line_index == loc.line then
      if rect.screen_line_rects then
        -- text
        for _,s in ipairs(rect.screen_line_rects) do
          for _,c in ipairs(s.char_rects) do
            if c.pos == loc.pos and (c.data or c.pos == utf8.len(line.data)+1) then
              return editor.left + c.x, y + c.y
            end
          end
        end
        assert(false, 'edit.to_coord: invalid pos in text loc')
      else
        -- drawing
        return editor.left, y + rect.y + Drawing_padding_top
      end
    end
    y = y + rect.dy
    if y > editor.bottom then
      break
    end
  end
end  -- 1 scan

-- find the location at the start of a screen line dy pixels down from loc
-- return nil if dy is more than screen height away
-- return bottommost screen line in file if we hit it
function edit.down(editor, loc, dy)  -- scans
  local y = 0
  local prevloc = loc
  for line_index, line in array.each(editor.lines, loc.line) do
    local rect = edit.get_rect(editor, {mode=line.mode, line=line_index, pos=1})
    if rect.screen_line_rects then
      -- text
      for _,s in ipairs(rect.screen_line_rects) do
        if line_index > loc.line or loc.pos < s.pos+s.dpos then
          local currloc = {mode='text', line=line_index, pos=s.pos}
          if y + s.dy > dy then
            return currloc
          end
          y = y + s.dy
          prevloc = currloc
        end
      end
    else
      -- drawing
      currloc = {mode='drawing', line=line_index}
      if y + rect.dy > dy then
        return currloc
      end
      y = y + rect.dy
      prevloc = currloc
    end
  end
  return prevloc
end  -- 1 scan

-- find the location at the start of a screen line dy pixels up from loc
-- return nil if dy is more than screen height away
-- return topmost screen line in file if we hit it
function edit.up(editor, loc, dy)  -- scans
  local y = 0
  -- special handling for loc's line
  local rect = edit.get_rect(editor, {mode=loc.mode, line=loc.line, pos=1})
  if rect.screen_line_rects then
    -- text
    local found = false
    for is = #rect.screen_line_rects,1,-1 do
      local s = rect.screen_line_rects[is]
      if not found and within(loc.pos, s.pos, s.pos+s.dpos) then
        found = true
      elseif found then
        if y + s.dy > dy then
          return {mode='text', line=loc.line, pos=s.pos}
        end
        y = y + s.dy
      else
        -- below loc's screen line; skip
      end
    end
  else
    -- drawing; skip
  end
  for line_index = loc.line-1,1,-1 do
    local line = editor.lines[line_index]
    local rect = edit.get_rect(editor, {mode=line.mode, line=line_index, pos=1})
    if rect.screen_line_rects then
      -- text
      for is = #rect.screen_line_rects,1,-1 do
        local s = rect.screen_line_rects[is]
        if y + s.dy > dy then
          return {mode='text', line=line_index, pos=s.pos}
        end
        y = y + s.dy
      end
    else
      -- drawing
      if y + rect.dy > dy then
        return {mode='drawing', line=line_index}
      end
      y = y + rect.dy
    end
  end
  return edit.top(editor)
end  -- 1 scan

-- find the location at the start of a screen line up to dy pixels up from loc, but count only whole screen lines.
-- So the result will be at or below dy pixels above loc.
function edit._up_whole_screen_lines(editor, loc, dy)  -- scans
  local prevloc = loc  -- bug: not at start of screen line
  local y = 0
  -- special handling for loc's line
  local rect = edit.get_rect(editor, {mode=loc.mode, line=loc.line, pos=1})
  if rect.screen_line_rects then
    -- text
    local found = false
    for is = #rect.screen_line_rects,1,-1 do
      local s = rect.screen_line_rects[is]
      if not found and within(loc.pos, s.pos, s.pos+s.dpos) then
        found = true
      elseif found then
        local currloc = {mode='text', line=loc.line, pos=s.pos}
        if y + s.dy > dy then
          return prevloc
        end
        y = y + s.dy
        prevloc = currloc
      else
        -- below loc's screen line; skip
      end
    end
  else
    -- drawing; skip
  end
  for line_index = loc.line-1,1,-1 do
    local line = editor.lines[line_index]
    local rect = edit.get_rect(editor, {mode=line.mode, line=line_index, pos=1})
    if rect.screen_line_rects then
      -- text
      for is = #rect.screen_line_rects,1,-1 do
        local s = rect.screen_line_rects[is]
        local currloc = {mode='text', line=line_index, pos=s.pos}
        if y + s.dy > dy then
          return prevloc
        end
        y = y + s.dy
        prevloc = currloc
      end
    else
      -- drawing
      currloc = {mode='drawing', line=line_index}
      if y + rect.dy > dy then
        return prevloc
      end
      y = y + rect.dy
      prevloc = currloc
    end
  end
  return edit.top(editor)
end  -- 1 scan

function edit.top(editor)
  assert(#editor.lines > 0)
  if editor.lines[1].mode == 'text' then
    return {mode='text', line=1, pos=1}
  else
    return {mode='drawing', line=1}
  end
end

-- find the location at x=x0 on the same screen line as loc
function edit.hor(editor, loc, x0)  -- scans line
  if loc.mode == 'drawing' then
    assert(editor.lines[loc.line].mode == 'drawing')
    return deepcopy(loc)
  end
  local rect = edit.get_rect(editor, {mode=loc.mode, line=loc.line, pos=1})
  x0 = x0 - editor.left
  assert(rect.screen_line_rects)
  for i,sc in ipairs(rect.screen_line_rects) do
    if loc.pos >= sc.pos and loc.pos < sc.pos+sc.dpos then
      local prevx = nil
      for _,c in ipairs(sc.char_rects) do
        if (prevx == nil or x0 >= (prevx+c.x)/2) and x0 < c.x+c.dx/2 then
          return {mode='text', line=loc.line, pos=c.pos}
        end
        prevx = c.x
      end
      return {mode='text', line=loc.line, pos=sc.pos+sc.dpos-1}
    end
  end
end  -- 0-1 scans

-- helper to check if space character at pos, x is final possible candidate
-- for line wrapping before x = editor.right
-- x lies between editor.left and editor.right
function Text.line_wrap_at_word_boundary(editor, x, line, pos)
  if x - editor.left > 0.8 * (editor.right - editor.left) then
    -- word boundary more than 80% of the way across.
    -- check if there's any more word boundaries before x gets to editor.right
    for pos, char in utf8chars(line, pos+1) do
      if x > editor.right then
        return true
      end
      local w = editor.font:getWidth(char)  -- width of char
      if char:match('%s') then
        if x+w < editor.right then
          break
        end
      end
      x = x+w
    end
  end
end

function edit.screen_line_height(editor, loc)
  if loc.mode == 'text' then
    return editor.line_height
  else
    local line = editor.lines[loc.line]
    assert(line.mode == 'drawing')
    return Drawing.height(editor, line)
  end
end

function Drawing.height(editor, line)
  return Drawing_padding_height + Drawing.pixels(line.h, editor.width)
end

function edit.eq(a, b)
  return a.mode == b.mode and a.line == b.line and --[[just for text mode]] a.pos == b.pos
end

function edit.lt(a, b)
  if a.line < b.line then
    return true
  end
  if a.line > b.line then
    return false
  end
  if a.mode == 'drawing' then
    return false  -- no further comparisons within drawings
  end
  return a.pos < b.pos
end

function edit.le(a, b)
  if a.line < b.line then
    return true
  end
  if a.line > b.line then
    return false
  end
  if a.mode == 'drawing' then
    return true  -- no further comparisons within drawings
  end
  return a.pos <= b.pos
end

function edit.get_rect(editor, loc)
  if loc.mode == 'text' then
    return Text.get_rect(editor, loc)
  else
    return {x=0, y=0, dx=editor.width, dy=edit.screen_line_height(editor, loc)}
  end
end

-- generate rects for each screen line in it and the range [pos,pos+dpos-1] associated with each
-- within each screen line generate rects for each char (utf8 codepoint) and the pos associated with each.
function Text.get_rect(editor, loc)
  local line = editor.lines[loc.line]
  assert(line.mode == 'text')
  local screen_lines = {}
  local curr_screen_line = {}
  local spos = 1
  local x, y = 0, 0
  for pos,char in utf8chars(line.data, loc.pos) do
    local w = editor.font:getWidth(char)
    if char:match('%s') then
      if Text.line_wrap_at_word_boundary(editor, editor.left + x, line.data, pos) then
        table.insert(curr_screen_line,
          {x=x, y=y, dx=w, dy=editor.line_height, pos=pos, data=char})  -- char
        table.insert(curr_screen_line,
          {x=x+w, y=y, dx=editor.width-x-w, dy=editor.line_height, pos=pos+1})  -- filler
        table.insert(screen_lines,
          {x=0, y=y, dx=editor.width, dy=editor.line_height,
           pos=spos, dpos=pos-spos+1, char_rects=curr_screen_line})
        curr_screen_line = {}
        spos = pos+1
        x = 0
        y = y + editor.line_height
        if y > editor.bottom - editor.top then
          return {x=0, y=0, dx=editor.width, dy=y, screen_line_rects=screen_lines}
        end
      else
        table.insert(curr_screen_line,
          {x=x, y=y, dx=w, dy=editor.line_height, pos=pos, data=char})
        x = x + w
      end
    else
      if x+w > editor.width then
        assert(pos > 1)
        table.insert(curr_screen_line,
          {x=x, y=y, dx=editor.width-x, dy=editor.line_height, pos=pos})  -- filler
        table.insert(screen_lines,
          {x=0, y=y, dx=editor.width, dy=editor.line_height,
           pos=spos, dpos=(pos-1)-spos+1, char_rects=curr_screen_line})
        curr_screen_line = {}
        spos = pos
        x = 0
        y = y + editor.line_height
        if y > editor.bottom - editor.top then
          return {x=0, y=0, dx=editor.width, dy=y, screen_line_rects=screen_lines}
        end
      else
        -- nothing
      end
      table.insert(curr_screen_line,
        {x=x, y=y, dx=w, dy=editor.line_height, pos=pos, data=char})
      x = x + w
    end
  end
  table.insert(curr_screen_line,
    {x=x, y=y, dx=editor.width-x, dy=editor.line_height, pos=utf8.len(line.data)+1})  -- filler
  table.insert(screen_lines,
    {x=0, y=y, dx=editor.width, dy=editor.line_height,
     pos=spos, dpos=utf8.len(line.data)+1-spos+1, char_rects=curr_screen_line})
  y = y + editor.line_height
  return {x=0, y=0, dx=editor.width, dy=y, line_index=loc.line, screen_line_rects=screen_lines}
end

function find_x(rects, x)
  if x < 0 then return rects[1] end
  for _, rect in ipairs(rects) do
    if within(x, rect.x, rect.x+rect.dx) then
      return rect
    end
  end
  return rects[#rects]
end

function find_y(rects, y)
  if y < 0 then return rects[1] end
  for _, rect in ipairs(rects) do
    if within(y, rect.y, rect.y+rect.dy) then
      return rect
    end
  end
  return rects[#rects]
end

function within_rect(rect, x,y)
  return within(x, rect.x, rect.x+rect.dx)
    and within(y, rect.y, rect.y+rect.dy)
end

function within(a, lo, hi)
  return a >= lo and a < hi
end

-- create a new iterator for s which provides the index and UTF-8 bytes corresponding to each codepoint
function utf8chars(s, startpos)
  local next_pos = startpos or 1  -- in code points
  local next_offset = utf8.offset(s, next_pos)  -- in bytes
  return function()
    assert(next_offset)  -- never call the iterator after it returns nil
    local curr_pos = next_pos
    next_pos = next_pos+1
    local curr_offset = next_offset
    next_offset = utf8.offset(s, 2, next_offset)
    if next_offset == nil then return end
    local curr_char = s:sub(curr_offset, next_offset-1)
    return curr_pos, curr_char
  end
end