一个高亮编辑框的构建历程

前言

制作背景

我已经在这之前多次写过高亮编辑框了,自从我入门编程以来,就一直在尝试自己造个高亮编辑框的轮子。
如果你不想看Rose无聊的背景叙述，请直接从侧栏跳到“本项目的开端”部分。

第一次尝试 - Editable

原理

这还是在我玩iApp的时候了。当时觉得一个高亮代码编辑框是iApp源码的一大空缺，所以打算造个源码。
初次的尝试对Android原生的控件还是抱有很大的期望的。所以选用了Android自带的TextView来制作。
众所周知，TextView自己就能显示不同颜色的文本，比如经常看到的链接就是一个例子。所以TextView拿来玩，
不存在原理上的问题。
因此，我们用Editable来设置文本颜色Spans，并且用TextView显示就好了。我们在文本更新时对高亮进行更新。
至于行号，我们只需要编辑框的左边加一个TextView就好了，然后在文本改变时生成文本设置就好了。
而滚动，只需要ScrollView和HorizontalScrollView套娃就行了。
再者，Spans的匹配只需要轻轻地写个正则表达式Pattern + Matcher就可以匹配了。

过程

于是我们造出了第一个高亮编辑框。这个编辑框比较原始，因为遇到一些转义的写法，字符串的高亮就可能发生错乱。下面是用于高亮SpannableStringBuilder的方法(Editable的唯一自带实现类)。代码只给出了一个类中的重要部分，自行移植。

//关键字，用|隔开
private String mBaseword = "instanceof|throw(s)?|new|continue|super|this|interface|abstract|public|private|protected|break|for|while|default|class|extends|implements|float|double|import|package|try|catch|finally|final|if|else|do|void|return|case|switch|null|false|true|static|int|byte|long|short";
//类名，用|隔开
private String mKeyword = "Override|Runnable|Thread|Activity|Context|Object|Integer|String|StringBuilder|CharSequence|Exception|Long|Short|Double|Float|Byte|Void";
//关键字颜色
private int mBasewordColor = Color.parseColor("#E91E63");
//类名颜色
private int mKeywordColor = Color.parseColor("#2196F3");
//数字颜色
private int mNumberColor = mBasewordColor;
//字符串颜色
private int mStringColor = mNumberColor;
//注释颜色
private int mCommentColor = Color.parseColor("#9e9e9e");
//没什么，用于连接字符串，编译关键字正则和类名正则
private Pattern getPattern(String content){return Pattern.compile("\\b("+content+")\\b");}
//关键字正则
private Pattern mBasewordPattern = getPattern(mBaseword);
//类名正则
private Pattern mKeywordPattern = getPattern(mKeyword);
//字符串正则
private Pattern mStringPattern = Pattern.compile("\\\"(.*?)\\\"|\\\'(.*?)\\\'");
//数字正则
private Pattern mNumberPattern = Pattern.compile("\\b(\\d*[.]?\\d+[|L|F|l|f]*)\\b");
//注释正则
private Pattern mCommentPattern = Pattern.compile("(\\/\\/.*|\\/\\*[\\s\\S]*?\\*\\/)");

//对于指定的SpannableStringBuilder进行高亮处理
private void highlight(SpannableStringBuilder sb)
{
  if(sb.length() == 0)//如果是空，就取消高亮
    return;
  try{
    clearSpans(sb);//清除spans
    for(Matcher m = mBasewordPattern.matcher(sb);m.find();)
      sb.setSpan(new ForegroundColorSpan(mBasewordColor),m.start(),m.end(),Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
    for(Matcher m = mKeywordPattern.matcher(sb);m.find();)
      sb.setSpan(new ForegroundColorSpan(mKeywordColor),m.start(),m.end(),Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
    for(Matcher m = mNumberPattern.matcher(sb);m.find();)
      sb.setSpan(new ForegroundColorSpan(mBasewordColor),m.start(),m.end(),Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
    for (Matcher m = mStringPattern.matcher(sb); m.find();)
    {
        ForegroundColorSpan[] spans = sb.getSpans(m.start(), m.end(), ForegroundColorSpan.class);
        for (ForegroundColorSpan span : spans)
          sb.removeSpan(span);
       sb.setSpan(new ForegroundColorSpan(mStringColor), m.start(), m.end(), Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
    }
    for(Matcher m = mCommentPattern.matcher(sb);m.find();)
      sb.setSpan(new ForegroundColorSpan(mCommentColor),m.start(),m.end(),Spannable.SPAN_EXCLUSIVE_EXCLUSIVE);
  }catch(Exception e){}
}

下面给出用于自动在回车时加入空格时的代码。同样只给出关键部分和方法：

public void setupAutoIndent(EditText et)
{
  InputFilter[] ifs = new InputFilter[]{
    new InputFilter()
    {
      public CharSequence filter(CharSequence source, int start, int end, Spanned dest, int dstart, int dend)
      {
        if (end - start == 1 && start < source.length() && dstart < dest.length())
        {
          char c = source.charAt(start);
          if(c == '\n')
            return autoIndent(source,dest,dstart,dend);
        }
        return source;
      }
  }};
  et.setFilters(ifs);
}

private CharSequence autoIndent(CharSequence source,Spanned dest,int dstart,int dend)
{
  String indent = "";
  int istart = dstart - 1;
  boolean dataBefore = false;
  int pt = 0;
  for (; istart > -1; --istart)
  {
    char c = dest.charAt(istart);
    if (c == '\n')
      break;
    if (c != ' ' &&c != '\t')
    {
      if (!dataBefore)
      {
        if (c == '{' ||c == '+' ||c == '-' ||c == '*' ||c == '/' ||c == '%' ||c == '^' ||c == '=')
          pt--;
        dataBefore = true;
      }
      if (c == '(')
        --pt;
      else if (c == ')')
        ++pt;
    }
  }
  if (istart > -1)
  {
    char charAtCursor = dest.charAt(dstart);
    int iend;
    for (iend = ++istart;iend < dend;++iend)
    {
      char c = dest.charAt(iend);
      if (charAtCursor != '\n' &&c == '/' &&iend + 1 < dend &&dest.charAt(iend) == c)
      {
        iend += 2;
        break;
      }
      if (c != ' ' &&c != '\t')
        break;
     }
   indent += dest.subSequence(istart, iend);
  }
  if (pt < 0)
    indent += "\t";
  return source + indent;
}

毕竟我们并没有真正的对它的语法进行分析，仅仅是正则匹配了一下而已。不但如此，虽然它在文本很少的时候效率很高，
我们使用起来就好像根本没有延迟一样，但是我们发现，文本一大，高亮的刷新就要很久，而且，由于我们在TextWatcher#afterTextChanged(Editable)中做我们的高亮刷新逻辑，实际上还是在UI线程，文本大了直接就把主线程给堵住了，用户无法进行交互，这无疑是最为恶劣的行径了。
我尝试在非主线程中刷新高亮，但是问题出现了–程序闪退了。
查看日志，原来TextView已经注册了SpanWatcher，当Editable中的Spans改变时，会导致TextView更新它的视图。
所以，当你在非UI线程对Spans进行修改时，会抛出来自ViewRootImple#checkThread()的异常，以阻止你非法更新视图。
总的来说，这一次已经实现了基本的高亮功能，但是存在诸多的弊端，尤其是用户体验不佳，所以该项目不佳。

弊端

高亮更新容易卡顿，并且可能错误
行号更新需要较多时间
滑动不顺畅，且不便于布局
每次增加一个Span都要重绘一次，资源占用高

第二次尝试 - 自定义View的开端

翻看开源项目

经过上一次尝试的失败后，我前去翻阅了TextWarrior（文侠）项目的源码（由于AndroLua+的使用，现在多数人称之为LuaEditor了，我也是在GitHub开源的Androlua-pro项目里面查看的）
无奈，看到关键的高亮部分却是看不懂了，打开LuaLexer我就傻眼了：这一大堆字符串常量都是些什么啊？还一堆什么什么静态的UnpackXxx()的方法，yylex()方法更是又臭又长,而且一堆case。于是我关闭了文件。
看不懂源码的我只能闭门造车，经过在CSDN、简书等地的多日学习，我总算摸明白了自定义View的套路。于是开始弄自己的编辑框。

闭门造车

然而，迫于当时自身技术所限，没能完成最终代码编辑框。仅仅是造了一个能显示文本和行号的编辑框而已，而且在翻动过程中，由于Index缓存算法的问题，可能随时抛出异常（必须的，当时我都没有考虑到文本的变化，所以如果编辑在显示区域之前的文本，必然在某时刻导致崩溃）。
本项目失败。

第三次尝试

不哔哔那么多，和第二次差不多了。但是能够流畅地显示大文本了，高达1000万行时不会出现绘制偏差了（经过查实，是float的精度问题，换成int就解决了）。
本次还添加了UndoManager用于管理Undo、Redo。顺便加了选择手柄，但是体验不佳。
重要的是，在这期间我可算知道了用于词法分析的工具–JFLex。
JFLex能够用正则表达式分析词法，给出一个词汇流。
我们不需要直接书写Java代码，而只需要写flex文件定义语法即可。

总结经验

Android原生的控件因为兼容性的关系，不能够很好地显示高亮代码（或者很麻烦），我们倾向于使用自定义View来显示它
高亮我们需要一个词法分析器来分析词法，才能绝对正确地识别文本的用法
float不能处理行数高于1.2kw左右的情况，会导致绘制的行位置产生偏差，大约每5行为一个误差周期

本项目的开端

在高一上学期期间，即2019年下半年，我死磕再一次写起了代码编辑框，这一次的原始想法是造一个Android IDE。
我在Eclipse建立了”EditorBase”工程,创建了ITextContent接口继承CharSequence，然后写了N个文件用ArrayList+StringBuilder的方式保存文本内容，实现了Insert、Delete和Replace操作，其中Replace直接调用Insert和Delete实现。UndoManager也重复实现了一遍。
本文含有大量源代码，懒得看的请点击语言左边的小按钮收起。

按行保存文本

主要是Insert、Delete。
其中的Cursor是稍后Android部分用到的工具，用于控制游标。
实现如下：

@Override
    public void insert(int line, int column, CharSequence text) {
        checkLineAndColumn(line, column, true);
        if (text == null) {
            throw new IllegalArgumentException("text can not be null");
        }

        //-----Notify------
        if(_cursor != null)
            _cursor.beforeInsert(line,column,text.length());

        int workLine = line;
        int workIndex = column;
        if(workIndex == -1){
            workIndex = 0;
        }
        StringBuilder currLine = _lines.get(workLine);
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c == '\n') {
                StringBuilder newLine = new StringBuilder();
                newLine.append(currLine, workIndex, currLine.length());
                currLine.delete(workIndex, currLine.length());
                _lines.add(workLine + 1, newLine);
                currLine = newLine;
                workIndex = 0;
                workLine++;
            } else {
                currLine.insert(workIndex, c);
                workIndex++;
            }
        }
        _textLength += text.length();
        this.dispatchAfterInsert(line, column, workLine, workIndex, text);
    }

    @Override
    public void delete(int startLine, int columnOnStartLine, int endLine, int columnOnEndLine) {
        StringBuilder changedContent = new StringBuilder();
        if (startLine == endLine) {
            checkLineAndColumn(endLine, columnOnEndLine, true);
            checkLineAndColumn(startLine, columnOnStartLine == -1 ? 0 : columnOnStartLine, true);
            int beginIdx = columnOnStartLine;
            int endIdx = columnOnEndLine;
            if (columnOnStartLine == -1) {
                beginIdx = 0;
            }
            if (beginIdx > endIdx) {
                throw new IllegalArgumentException("start > end");
            }
            StringBuilder curr = _lines.get(startLine);
            int len = curr.length();
            if (beginIdx < 0 || endIdx < 0 || beginIdx > len || endIdx > len) {
                throw new StringIndexOutOfBoundsException("column start or column end is out of bounds");
            }

            //-----Notify------
            if(_cursor != null)
                if(columnOnStartLine != -1)
                    _cursor.beforeDelete(startLine,columnOnStartLine,endLine,columnOnEndLine);
                else
                    _cursor.beforeDelete(startLine == 0 ? 0 : startLine - 1,startLine == 0 ? 0 : getColumnCount(startLine - 1),endLine,columnOnEndLine);

            changedContent.append(curr, beginIdx, endIdx);
            curr.delete(beginIdx, endIdx);
            _textLength -= columnOnEndLine - columnOnStartLine;
            if (columnOnStartLine == -1) {
                if (startLine == 0) {
                    _textLength++;
                } else {
                    StringBuilder previous = _lines.get(startLine - 1);
                    previous.append(curr);
                    _lines.remove(startLine);
                    changedContent.insert(0, '\n');
                    startLine--;
                    columnOnStartLine = getColumnCount(startLine);
                }
            }
        } else if (startLine < endLine) {
            checkLineAndColumn(startLine, columnOnStartLine, true);
            checkLineAndColumn(endLine, columnOnEndLine, true);

            //-----Notify------
            if(_cursor != null)
                _cursor.beforeDelete(startLine,columnOnStartLine,endLine,columnOnEndLine);

            int currEnd = endLine;
            while (currEnd - 1 != startLine) {
                StringBuilder line = _lines.remove(currEnd - 1);
                _textLength -= line.length() + 1;
                changedContent.append('\n').append(line);
                currEnd--;
            }
            StringBuilder start = _lines.get(startLine);
            StringBuilder end = _lines.get(currEnd);
            _textLength -= start.length() - columnOnStartLine;
            changedContent.insert(0, start, columnOnStartLine, start.length());
            start.delete(columnOnStartLine, start.length());
            _textLength -= columnOnEndLine;
            changedContent.append('\n').append(end, 0, columnOnEndLine);
            end.delete(0, columnOnEndLine);
            _textLength--;
            _lines.remove(currEnd);
            start.append(end);
        } else {
            throw new IllegalArgumentException("start line > end line");
        }
        this.dispatchAfterDelete(startLine, columnOnStartLine, endLine, columnOnEndLine, changedContent);
    }

    @Override
    public void replace(int startLine, int columnOnStartLine, int endLine, int columnOnEndLine, CharSequence text) {
        if (text == null) {
            throw new IllegalArgumentException("text can not be null");
        }
        this.dispatchBeforeReplace();
        delete(startLine, columnOnStartLine, endLine, columnOnEndLine);
        insert(startLine, columnOnStartLine, text);
    }

实现Index<->(Line,Column)的变换

它的精彩之处不在于保存文本的方式，而在于index和行列对的转换。
我们使用了Indexer接口定义转换器。它拥有多个实现，包括：CachedIndexer和NoCacheIndexer。NoCacheIndex直接继承CachedIndexer并且关闭缓存即可。
CachedIndexer可以监听文本内容的变化。
这是CachedIndexer的部分代码（不关键的部分已删去）。主要是从缓存进行查询的步骤可以看一看。
其中更新缓存的代码可能有误，请到仓库查看最新实现。

class CachedIndexer implements Indexer,ContentListener{

    private Content _c;
    private CharPosition _zero = new CharPosition().zero();
    private List<CharPosition> _cache = new ArrayList<>();
    private int _switchIndex = 50;
    private int _switchLine = 50;
    private int _maxSize = 50;
    
    private CharPosition findIndexForward(CharPosition start,int index) {
        if(start.index > index) {
            throw new IllegalArgumentException("Unable to find backward from method findIndexForward()");
        }
        int workLine = start.line;
        int workColumn = start.column;
        int workIndex = start.index;
        //Move the column to the line end
        {
            int column = _c.getColumnCount(workLine);
            workIndex += column - workColumn;
            workColumn = column;
        }
        while(workIndex < index) {
            workLine++;
            workColumn = _c.getColumnCount(workLine);
            workIndex += workColumn + 1;
        }
        if(workIndex > index) {
            workColumn -= workIndex - index;
        }
        CharPosition pos = new CharPosition();
        pos.column = workColumn;
        pos.line = workLine;
        pos.index = index;
        return pos;
    }

    private CharPosition findIndexBackward(CharPosition start,int index) {
        if(start.index < index) {
            throw new IllegalArgumentException("Unable to find forward from method findIndexBackward()");
        }
        int workLine = start.line;
        int workColumn = start.column;
        int workIndex = start.index;
        while(workIndex > index) {
            workIndex -= workColumn + 1;
            workLine--;
            if(workLine != -1) {
                workColumn = _c.getColumnCount(workLine);
            }else {
                //Reached the start of text,we have to use findIndexForward() as this method can not handle it
                return findIndexForward(_zero,index);
            }
        }
        int dColumn = index - workIndex;
        if(dColumn > 0) {
            workLine++;
            workColumn = dColumn - 1;
        }
        CharPosition pos = new CharPosition();
        pos.column = workColumn;
        pos.line = workLine;
        pos.index = index;
        return pos;
    }

    private CharPosition findLiCoForward(CharPosition start,int line,int column) {
        if(start.line > line) {
            throw new IllegalArgumentException("can not find backward from findLiCoForward()");
        }
        int workLine = start.line;
        int workIndex = start.index;
        {
            //Make index to to left of line
            workIndex = workIndex - start.column;
        }
        while(workLine < line) {
            workIndex += _c.getColumnCount(workLine) + 1;
            workLine ++;
        }
        CharPosition pos = new CharPosition();
        pos.column = 0;
        pos.line = workLine;
        pos.index = workIndex;
        return findInLine(pos, line, column);
    }

    private CharPosition findLiCoBackward(CharPosition start,int line,int column) {
        if(start.line < line) {
            throw new IllegalArgumentException("can not find forward from findLiCoBackward()");
        }
        int workLine = start.line;
        int workIndex = start.index;
        {
            //Make index to the left of line
            workIndex = workIndex - start.column;
        }
        while(workLine > line) {
            workIndex -= _c.getColumnCount(workLine - 1) + 1;
            workLine--;
        }
        CharPosition pos = new CharPosition();
        pos.column = 0;
        pos.line = workLine;
        pos.index = workIndex;
        return findInLine(pos, line, column);
    }

    private CharPosition findInLine(CharPosition pos,int line,int column) {
        if(pos.line != line) {
            throw new IllegalArgumentException("can not find other lines with findInLine()");
        }
        int index = pos.index - pos.column + column;
        CharPosition pos2 = new CharPosition();
        pos2.column = column;
        pos2.line = line;
        pos2.index = index;
        return pos2;
    }

    @Override
    public CharPosition getCharPosition(int index) {
        _throw();
        _c.checkIndex(index);
        CharPosition pos = findNeareatByIndex(index);
        CharPosition res;
        if(pos.index == index) {
            return pos;
        }else if(pos.index < index) {
            res = findIndexForward(pos, index);
        }else {
            res = findIndexBackward(pos, index);
        }
        if(Math.abs(index - pos.index) >= _switchIndex) {
            push(res);
        }
        return res;
    }

    @Override
    public CharPosition getCharPosition(int line, int column) {
        _throw();
        _c.checkLineAndColumn(line, column, true);
        CharPosition pos = findNeareastByLine(line);
        CharPosition res;
        if(pos.line == line) {
            if(pos.column == column) {
                return pos;
            }
            return findInLine(pos,line,column);
        }else if(pos.line < line) {
            res = findLiCoForward(pos, line, column);
        }else {
            res = findLiCoBackward(pos, line, column);
        }
        if(Math.abs(pos.line - line) > _switchLine) {
            push(res);
        }
        return res;
    }

    @Override
    public void afterInsert(Content content, int startLine, int startColumn, int endLine, int endColumn,
                            CharSequence insertedContent) {
        if(isHandleEvent()) {
            for(CharPosition pos : _cache) {
                if(pos.line == startLine){
                    if (pos.column >= startColumn) {
                        pos.index += insertedContent.length();
                        pos.line += endLine - startLine;
                        pos.column = endColumn + pos.column - startColumn;
                    }
                }else if(pos.line > startLine) {
                    pos.index += insertedContent.length();
                    pos.line += endLine - startLine;
                }
            }
        }
        _detectException();
    }

    @Override
    public void afterDelete(Content content, int startLine, int startColumn, int endLine, int endColumn,
                            CharSequence deletedContent) {
        if(isHandleEvent()) {
            List<CharPosition> garbbages = new ArrayList<>();
            for(CharPosition pos : _cache) {
                if(pos.line == startLine) {
                    if(pos.column >= startColumn)
                        garbbages.add(pos);
                }else if(pos.line > startLine) {
                    if(pos.line < endLine) {
                        garbbages.add(pos);
                    }else if(pos.line == endLine) {
                        garbbages.add(pos);
                    }else {
                        pos.index -= deletedContent.length();
                        pos.line -= endLine - startLine;
                    }
                }
            }
            _cache.removeAll(garbbages);
            garbbages.clear();
        }
        _detectException();
    }

}

本次的意义在于从基层实现了(Line,Column)与Index的互查，仍然采用的是缓存来加速，但实现了更新缓存的逻辑。（尽管很弱）

Undo和Redo

Undo/Redo功能也适宜在最底层实现了。我们使用UndoManager来管理这些操作。
我们知道，用户输入文本总是一点一点地输入的，如果每一次修改都记录的话，那么要恢复操作的时候肯定Undo、Redo就得被狂按了。
所以，我们必须合并这些操作。而且，我们保存的操作不能太多，要不然用户多写一堆东西，咱们可就OOM喽！
所以，我们为Stack设定一个最大大小。
此外，输入法还有功能是批量操作。典型例子就是当你接入外接键盘到你的手机上的时候，你的输入法会变成一条。这个时候，你输入的拼音不是显示在你的输入法窗口中而是直接就显示在了我们的输入框里面。在输入法把拼音提交给输入框之前，会先通过InputConnection#beginBatchEdit()来通知你开始批量输入，这个方法的返回值是boolean。如果你在这个时候返回false，那拼音就输入不了了喽！而且输入法会变成只能输入英文和符号了！！！典型的例子就是AIDE了，在我的凤凰OS上就只能输入英文，如果想输入中文，我就只能复制粘贴了。所以，实现beginBatchEdit()和endBatchEdit()是有必要的。
在我们继承的BaseInputConnection中，beginBachEdit()和endBatchEdit()都是空实现!
根据Android开发文档，batchEdit可以嵌套，而且在endBatchEdit()方法中,有些”behave”不良的输入法可能到导致我们的nestedBatchEdit数值小于0,这个时候,你不能让它小于0!而在finishComposingText()中你必须结束所有的BatchEdit
在batchEdit时,我们应该合并所有操作为一个操作。
以上方法均在InputConnection中定义过了，可以参阅。

final class UndoManager implements ContentListener {
    private Content _c;
    private boolean _undoEnabled;
    private int _maxStackSize;
    private List<ContentAction> _undoStack;
    private InsertAction _insertAction;
    private DeleteAction _deleteAction;
    private boolean _replace;
    private int _undoPos;
    private boolean _ignore;

    protected UndoManager(Content content) {
        _c = content;
        _undoStack = new ArrayList<>();
        _replace = false;
        _insertAction = null;
        _deleteAction = null;
        _undoPos = 0;
        _ignore = false;
    }

    public void undo(Content content) {
        if(canUndo()) {
            _ignore = true;
            _undoStack.get(_undoPos - 1).undo(content);
            _undoPos--;
            _ignore = false;
        }
    }

    public void redo(Content content) {
        if(canRedo()) {
            _ignore = true;
            _undoStack.get(_undoPos).redo(content);
            _undoPos++;
            _ignore = false;
        }
    }

    public boolean canUndo() {
        return isUndoEnabled() && (_undoPos > 0);
    }

    public boolean canRedo() {
        return isUndoEnabled() && (_undoPos < _undoStack.size());
    }

    public void setUndoEnabled(boolean enabled) {
        _undoEnabled = enabled;
        if (!enabled) {
            cleanStack();
        }
    }

    public boolean isUndoEnabled() {
        return _undoEnabled;
    }

    public void setMaxUndoStackSize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException(
                    "max size can not be zero or smaller.Did you want to disable undo module by calling set_undoEnabled(false)?");
        }
        _maxStackSize = maxSize;
        cleanStack();
    }

    public int getMaxUndoStackSize() {
        return _maxStackSize;
    }

    private void cleanStack() {
        if(!_undoEnabled) {
            _undoStack.clear();
            _undoPos = 0;
        }else {
            while(_undoPos > 1 && _undoStack.size() > _maxStackSize) {
                _undoStack.remove(0);
                _undoPos--;
            }
        }
    }

    private void cleanBeforePush() {
        while(_undoPos < _undoStack.size()) {
            _undoStack.remove(_undoStack.size() - 1);
        }
    }

    private void _push(ContentAction action) {
        if(!isUndoEnabled()) {
            return;
        }
        cleanBeforePush();
        if(_c.isInBatchEdit()) {
            if(_undoStack.isEmpty()) {
                MultiAction a = new MultiAction();
                a.addAction(action);
                _undoStack.add(a);
                _undoPos++;
            }else {
                ContentAction a = _undoStack.get(_undoStack.size() - 1);
                if(a instanceof MultiAction) {
                    MultiAction ac = (MultiAction)a;
                    ac.addAction(action);
                }else {
                    MultiAction ac = new MultiAction();
                    ac.addAction(action);
                    _undoStack.add(ac);
                    _undoPos++;
                }
            }
        }else {
            if(_undoStack.isEmpty()) {
                _undoStack.add(action);
                _undoPos++;
            }else {
                ContentAction last = _undoStack.get(_undoStack.size() - 1);
                if(last.canMerge(action)) {
                    last.merge(action);
                }else {
                    _undoStack.add(action);
                    _undoPos++;
                }
            }
        }
        cleanStack();
    }

    @Override
    public void beforeReplace(Content content) {
        if(_ignore) {
            return;
        }
        _replace = true;
    }

    @Override
    public void afterInsert(Content content, int startLine, int startColumn, int endLine, int endColumn,
                            CharSequence insertedContent) {
        if(_ignore) {
            return;
        }
        _insertAction = new InsertAction();
        _insertAction.startLine = startLine;
        _insertAction.startColumn = startColumn;
        _insertAction.endLine = endLine;
        _insertAction.endColumn = endColumn;
        _insertAction.text = insertedContent;
        if(_replace) {
            ReplaceAction rep = new ReplaceAction();
            rep._delete = _deleteAction;
            rep._insert = _insertAction;
            _push(rep);
        }else {
            _push(_insertAction);
        }
        _replace = false;
    }

    @Override
    public void afterDelete(Content content, int startLine, int startColumn, int endLine, int endColumn,
                            CharSequence deletedContent) {
        if(_ignore) {
            return;
        }
        _deleteAction = new DeleteAction();
        _deleteAction.endColumn = endColumn;
        _deleteAction.startColumn = startColumn;
        _deleteAction.endLine = endLine;
        _deleteAction.startLine = startLine;
        _deleteAction.text = deletedContent;
        if(!_replace) {
            _push(_deleteAction);
        }
    }

}

所有应该实现的基础至此都已实现，剩下的就是Android部分了。

初构Android

文本绘制和基本交互

绘制的坑

作为Android的重头戏，咱们必须了解的是文本绘制啊！
首先先来了解一下文本绘制中的巨坑。
以下是来自BaseCanvas(android.graphics)的一段关于drawText的代码：

    public void drawText(@NonNull CharSequence text, int start, int end, float x, float y,
        @NonNull Paint paint) {
    if ((start | end | (end - start) | (text.length() - end)) < 0) {
        throw new IndexOutOfBoundsException();
    }
    throwIfHasHwBitmapInSwMode(paint);
    if (text instanceof String || text instanceof SpannedString ||
            text instanceof SpannableString) {
        nDrawText(mNativeCanvasWrapper, text.toString(), start, end, x, y,
                paint.mBidiFlags, paint.getNativeInstance());
    } else if (text instanceof GraphicsOperations) {
        ((GraphicsOperations) text).drawText(this, start, end, x, y,
                paint);
    } else {
        char[] buf = TemporaryBuffer.obtain(end - start);
        TextUtils.getChars(text, start, end, buf, 0);
        nDrawText(mNativeCanvasWrapper, buf, 0, end - start, x, y,
                paint.mBidiFlags, paint.getNativeInstance());
        TemporaryBuffer.recycle(buf);
    }
}

注意到第二个if里面的语句。我们发现，在传递文本给nDrawText()方法之前，String、SpannedString或者SpannableString都会被toString()一次！只要文本一长，在这个方法上牺牲的时间是很大的！
上一次写编辑框的时候就被这个toString()坑到了，在OPPO R7s上绘制几百行（只绘制可见区域，相当于有上百次的drawText()的提交），竟然到了1秒钟不能上24fps的地步（超过了绿线）。
我觉得不可能啊,于是又在Paint中发现了蹊跷:

public float measureText(CharSequence text, int start, int end) {
        if (text == null) {
            throw new IllegalArgumentException("text cannot be null");
        }
        if ((start | end | (end - start) | (text.length() - end)) < 0) {
            throw new IndexOutOfBoundsException();
        }

        if (text.length() == 0 || start == end) {
            return 0f;
        }
        if (text instanceof String) {
            return measureText((String)text, start, end);
        }
        if (text instanceof SpannedString ||
            text instanceof SpannableString) {
            return measureText(text.toString(), start, end);
        }
        if (text instanceof GraphicsOperations) {
            return ((GraphicsOperations)text).measureText(start, end, this);
        }

        char[] buf = TemporaryBuffer.obtain(end - start);
        TextUtils.getChars(text, start, end, buf, 0);
        float result = measureText(buf, 0, end - start);
        TemporaryBuffer.recycle(buf);
        return result;
    }

原来Paint中也有如出一辙的操作!
再考虑到咱们自身绘制方法本来就有问题，提交次数太多了：我们是一个一个字符绘制的。
每个字符都必须要drawText() + measureText()来实现OffsetX的转义。
节约的绘制远远比不上咱们一个字一个字提交绘制的时间，所以自然绘制就十分卡顿了。
emmmm…
这里必须提嘴一句的是,TextWarrior的绘制方式好像也是一个字一个字地绘制,不过他们用的不是直接提交CharSequence,而是提交一个长度为1或2的(为了支持Emoji时)char[],避免了这一问题。但是绘制时间稍微有些长了。
扯完了上面这些，我们先来快速了解一下Android的文本绘制吧。
文本绘制的关键在于用上baseline（基线）。
baseline大抵相当于英文里面四线三格的第三条线，我们drawText要传入的就是这条线在画布上的位置。
baseline怎么获取呢？
下面这样就好了（其中mPaint是画笔对象，获取的值因Text Size而改变）：

/**
 * Get line height
 * @return height of single line
 */
public int getLineHeight(){
    return mPaint.getFontMetricsInt().descent - mPaint.getFontMetricsInt().ascent;
}

/**
 * Get baseline directly
 * @param line Line
 * @return baseline y offset
 */
public int getLineBaseLine(int line){
    return getLineHeight() * (line + 1) - mPaint.getFontMetricsInt().descent;
}

当然,绘制的时候你还需要减去当前的X偏移量。
下面再给出获取其它几个量的方法：

/**
 * Get line top y offset
 * @param line Line
 * @return top y offset
 */
public int getLineTop(int line){
    return getLineHeight() * line;
}

/**
 * Get line bottom y offset
 * @param line Line
 * @return Bottom y offset
 */
public int getLineBottom(int line){
    return getLineHeight() * (line + 1);
}

下一个需要了解的是Paint.Align
这有关我们传入给drawText()的X坐标。
有些人总以为这个X左边很简单，就是文本绘制的左边，事实上不是这样的。它因Paint.Align的变化而变化。
Paint.Align是一个枚举类。
有：LEFT,RIGHT,CENTER
都是什么意思呢?
LEFT:传入的X坐标是文本绘制的左坐标
RIGHT:传入的X坐标是文本绘制的右坐标
CENTER:传入的X坐标是文本绘制的中心坐标(文本的横向中心X坐标为这个X值)

绘制行号

绘制行号的时候,我们会用到它。
下面给出行号的绘制方法:
canvas:画布
offsetX:行号区域在画布上的起始坐标
width:最宽的行号的宽度,代表了行号区域的宽度
color:行号的颜色

/**
 * Draw line numbers on screen
 * @param canvas Canvas to draw
 * @param offsetX Start region of line number region
 * @param width The width of line number region
 * @param color Color of line number
 */
private void drawLineNumbers(Canvas canvas, float offsetX, float width, int color){
    if(width + offsetX <= 0){
        return;
    }
    int first = getFirstVisibleLine();
    int last = getLastVisibleLine();
    mPaint.setTextAlign(mLineNumberAlign);
    mPaint.setColor(color);
    mPaint.setTypeface(mTypefaceLineNumber);
    for(int i = first;i <= last;i++){
        switch(mLineNumberAlign){
            case LEFT:
                canvas.drawText(Integer.toString(i + 1), offsetX, getLineBaseLine(i) - getOffsetY(), mPaint);
                break;
            case RIGHT:
                canvas.drawText(Integer.toString(i + 1), offsetX + width, getLineBaseLine(i) - getOffsetY(), mPaint);
                break;
            case CENTER:
                canvas.drawText(Integer.toString(i + 1), offsetX + width / 2f, getLineBaseLine(i) - getOffsetY(), mPaint);
        }
    }
    mPaint.setTextAlign(Paint.Align.LEFT);
}

滚动操作

作为一个现实文本的工具,没有滚动怎么行?超出区域不就再也看不见了!
但是自己实现滚动,又必须考虑到用户的滚动手势!光拖拽怎么行?
没关系,Android已经给我们造好了轮子!
我们只需要使用Scroller(这里我们为了一些边缘效果,使用了OverScroller,两者皆在android.widget包下,没有继承关系,用法基本相同,OverScroller功能稍多)来执行滚动操作,
使用GestureDetector来实现手势的识别.
使用方法也很简单:
定义成员变量:

1	private GestureDetector mBasicDetector;

在初始化咱们自己的View时:

1 2	mBasicDetector = new GestureDetector(getContext(), mEventHandler); mBasicDetector.setOnDoubleTapListener(mEventHandler);

EventHandler需要实现:GestureDetector.OnGestureListener,GestureDetector.OnDoubleTapListener
然后让它代替我们响应触摸事件:

@Override
@SuppressLint("ClickableViewAccessibility")
protected boolean onTouchEvent(MotionEvent event) {
    return mBasicDetector.onTouchEvent(event);
}

不过这么做,OnClickListener会失效.
我们将会在EventHandler的onSingleTapUpConfirmed(MotionEvent)方法中得到单击的通知
** onSingleTapUp() 和 onSingleTapUpConfirmed() 的区别 ** :
onSingleTapUp()仅仅是表达用户点击了我们的视图,但是不知道是不是连击
而onSingleTapUpConfirmed()表示用户确确实实单击了我们的视图,不存在连击
双击事件会在onDoubleTap()和onDoubleTapEvent()则是控制双击事件的,我们不做处理.
我们现在要做的,仅仅是滚动.
在EventHandler中写道:

@Override
public boolean onDown(MotionEvent e) {
    return mEditor.isEnabled();
}

@Override
public boolean onScroll(MotionEvent e1, MotionEvent e2, float distanceX, float distanceY) {
    int endX = mScroller.getCurrX() + (int)distanceX;
    int endY = mScroller.getCurrY() + (int)distanceY;
    endX = Math.max(endX,0);
    endY = Math.max(endY,0);
    endY = Math.min(endY,mEditor.getScrollMaxY());
    endX = Math.min(endX,mEditor.getScrollMaxX());
    mScroller.startScroll(mScroller.getCurrX(),
            mScroller.getCurrY(),
            endX - mScroller.getCurrX(),
            endY - mScroller.getCurrY(),0);
    mEditor.invalidate();
    return true;
}

@Override
public boolean onFling(MotionEvent e1, MotionEvent e2, float velocityX, float velocityY) {
    mScroller.fling(mScroller.getCurrX(),
            mScroller.getCurrY(),
            (int)-velocityX,
            (int)-velocityY,
            0,
            mEditor.getScrollMaxX(),
            0,
            mEditor.getScrollMaxY(),
            20,
            20);
    mEditor.invalidate();
    return false;
}

其中mScroller是我们OverScroller对象
mEditor是我们的编辑框对象
getScrollMaxY()和getScrollMaxX()定义在编辑框类中,
getScrollMaxY()我们返回getLineHeight() * getLineCount() - getHeight() / 2 ,让用户有额外半屏滑动,便于编辑
getScrollMaxX()我们返回mMaxPaintX - getWidth()/2(mMaxPaintX:历史最大的绘制X)
上面通过Scroller实现的惯性滑动效果,必须在编辑框类中做一点小处理才行:

@Override
public void computeScroll() {
    if(mEventHandler.getScroller().computeScrollOffset()){
        invalidate();
    }
    super.computeScroll();
}

如果不加上面的代码,那么惯性滑动就不会看到了(除非我们再一次invalidate()).
因为我们没有持续绘制.
computeScroll()会在绘制阶段被调用,我们得以持续绘制动画.

初步绘制文本

终于到了绘制文本的阶段了,我们调试编辑框,最先就是得把文本画出来啊!要不然,怎么看得到效果呢?
由于是初步绘制用于调试,我们先不实现高亮,只实现绘制.
但是,为了性能考虑,我们应该只绘制可见部分的行才对:

/**
 * Get first visible line on screen
 * @return first visible line
 */
public int getFirstVisibleLine(){
    int j = Math.min(getOffsetY() / getLineHeight(), getLineCount() - 1);
    if(j < 0){
        return 0;
    }else{
        return j;
    }
}

/**
 * Get last visible line on screen
 * @return last visible line
 */
public int getLastVisibleLine(){
    int l = Math.min((getOffsetY() + getHeight()) / getLineHeight(), getLineCount() - 1);
    if(l < 0){
        return 0;
    }else{
        return l;
    }
}

下面是简单绘制文本的方法:
为了防止一些坑,我们定义成员变量mChars临时保存正在绘制的行的具体内容,绘制这一行之前,我们调用prepareLine(int)来填充这一行的内容到mChars
然后,我们调用我们自己定义的drawText方法绘制,以便显示出Tab.最后,用我们自己的方法测量出这一行的宽带,尝试更新最大的滚动X值
canvas:画布
offsetX:在屏幕上的起始位置
color:文字颜色
startLine:第一个要绘制的行

/**
 * Draw text without any spans
 * @param canvas Canvas to draw
 * @param offsetX Start x of text region
 * @param color Color to draw text
 * @param startLine The start line to paint
 */
private void drawTextDirect(Canvas canvas, float offsetX, int color, int startLine){
    mPaint.setColor(color);
    mPaint.setTypeface(mTypefaceText);
    int last = getLastVisibleLine();
    for(int i = startLine;i <= last;i++){
        if(mText.getColumnCount(i) == 0){
            continue;
        }
        prepareLine(i);
        drawText(canvas, mChars, 0, mText.getColumnCount(i), offsetX, getLineBaseLine(i) - getOffsetY());
        float width = measureText(mChars,0,mText.getColumnCount(i)) + offsetX;
        if(width > mMaxPaintX) {
            mMaxPaintX = width;
        }
    }
}

/**
 * Read characters to mChars for the given line
 * @param line Line going to draw or measure
 */
private void prepareLine(int line){
    int length = mText.getColumnCount(line);
    if(length >= mChars.length){
        mChars = new char[length + 100];
    }
    for(int i = 0;i < length;i++){
        mChars[i] = mText.charAt(line, i);
    }
}

/**
 * Draw text on the given position
 * @param canvas Canvas to draw
 * @param src Source of characters
 * @param index The index in array
 * @param count Count of characters
 * @param offX Offset x for paint
 * @param offY Offset y for paint(baseline)
 */
private void drawText(Canvas canvas, char[] src, int index, int count, float offX, float offY){
    int end = index + count;
    int st = index;
    for(int i = index;i < end;i++) {
        if(src[i] == '\t') {
            canvas.drawText(src,st,i - st,offX,offY,mPaint);
            offX = offX + measureText(src,st,i - st + 1);
            st = i + 1;
        }
    }
    if(st < end) {
        canvas.drawText(src,st,end - st,offX,offY,mPaint);
    }
}

/**
 * Measure text width
 * @param src Source characters array
 * @param index Start index in array
 * @param count Count of characters
 * @return The width measured
 */
private float measureText(char[] src, int index, int count){
    mPaint.setTypeface(mTypefaceText);
    float extraWidth;
    int tabCount = 0;
    for(int i = 0;i < count;i++){
        if(src[index + i] == '\t'){
            tabCount++;
        }
    }
    if(count > 0 && isEmoji(src[index + count - 1])) {
        count--;
        if(count < 0) {
            count = 0;
        }
    }
    extraWidth = mSpaceWidth * (getTabWidth() - 1);
    return mPaint.measureText(src, index, count) + tabCount * extraWidth;
}

/**
 * Check whether the given character is a start sign for emoji
 * @param ch Character to check
 * @return Whether this is leading a emoji
 */
private static boolean isEmoji(char ch){
    return ch == 0xd83c || ch == 0xd83d;
}

至此,一个能显示文本和行号外加分割线的编辑框的绘制部分就基本完成了!
下面我们来控制输入:

实现输入和删除

首先必须让别人知道我们是个输入框才行:

@Override
public boolean onCheckIsTextEditor() {
    return isEnabled() && isEditable();
}

让后创建我们自己的InputConnection类:

@Override
public InputConnection onCreateInputConnection(EditorInfo outAttrs) {
    if(!isEditable() || !isEnabled()){
        return null;
    }
    outAttrs.inputType = EditorInfo.TYPE_TEXT_FLAG_MULTI_LINE;
    mConnection.reset();
    return mConnection;
}

为了方便,我们自己的Connection只创建一次,后面直接重置.根据测试,如果总是返回创建的新对象,后面我们发现这回导致第一次启动输入的时候无法获取到ComposingText的位置(在我们的Connection保存和自动修改的)
后面直接reset()重置状态即可.
其中setComposingText()就是我们为了实现ComposingText位置获取的逻辑了.ComposingText中不存在回车/换行.
Cursor是游标,可进仓库查看具体实现.Left指左游标,Right指右游标,set()设置两个游标.

class RoseEditorInputConnection extends BaseInputConnection {

    private RoseEditor mEditor;

    private int actionCode = -1;

    private int length = -1;

    private StringBuilder commit = new StringBuilder();
    protected int composingLine = -1;
    protected int composingStart = -1;
    protected int composingEnd = -1;

    /**
     * Create a connection for the given editor
     * @param targetView Host editor
     */
    public RoseEditorInputConnection(RoseEditor targetView) {
        super(targetView, true);
        mEditor = targetView;
        finishComposingText();
    }

    /**
     * Reset the state of this connection
     */
    protected void reset(){
        commit = new StringBuilder();
        composingEnd = composingStart = composingLine = -1;
        actionCode = -1;
        length = -1;
    }

    /**
     * Private use.
     * Get the Cursor of Content displaying by Editor
     * @return Cursor
     */
    private Cursor getCursor(){
        return mEditor.getCursor();
    }

    @Override
    public void closeConnection() {
        super.closeConnection();
        mEditor.onCloseConnection();
    }

    @Override
    public boolean commitText(CharSequence text, int newCursorPosition) {
        if(text == null){
            return false;
        }
        if(mEditor.isEditable()){
            if(composingLine != -1){
                commit.append(text);
                return true;
            }
            getCursor().onCommitText(text);
            actionCode = 0;
            length = text.length();
        }
        return mEditor.isEditable();
    }

    @Override
    public boolean deleteSurroundingText(int beforeLength, int afterLength) {
        if(mEditor.isEditable()){
            getCursor().onDeleteKeyPressed();
            actionCode = 1;
        }
        return mEditor.isEditable();
    }

    @Override
    public boolean beginBatchEdit() {
        return mEditor.getText().beginBatchEdit();
    }

    @Override
    public boolean endBatchEdit() {
        return mEditor.getText().endBatchEdit();
    }

    @Override
    public boolean setComposingText(CharSequence text, int newCursorPosition)
    {
        if(!mEditor.isEditable()){
            return false;
        }
        if(text == null){
            finishComposingText();
            return true;
        }
        if(composingLine == -1){
            commit = new StringBuilder();
            if(getCursor().isSelected())
                getCursor().onDeleteKeyPressed();
            composingLine = mEditor.getCursor().getRightLine();
            composingStart = mEditor.getCursor().getRightColumn();
            composingEnd = composingStart + text.length();
            getCursor().onCommitText(text);
        }else{
            getCursor().setLeft(composingLine,composingStart);
            getCursor().setRight(composingLine,composingEnd);
            composingEnd = composingStart + text.length();
            getCursor().onCommitText(text);
        }
        return true;
    }

    @Override
    public boolean finishComposingText(){
        composingStart = -1;
        composingEnd = -1;
        composingLine = -1;
        if(commit.length() != 0){
            getCursor().onCommitText(commit);
            commit = new StringBuilder();
        }
        return true;
    }

    @Override
    public boolean setSelection(int start, int end) {
        if(actionCode == 0 && length == 2){
            Cursor cur = getCursor();
            cur.setLeft(cur.getLeftLine(),cur.getLeftColumn() - 1);
            return true;
        }
        return false;
    }
}

我们发现,回车迟迟输入不了,这是为什么呢?
我们覆盖InputConnection#sendKeyEvent(),弹出Toast发现:回车和删除通过KeyEvent发送.
注意到BaseInputConnection已经实现了KeyEvent派遣到我们View的逻辑,只需要在我们的View里面重写:

@Override
public boolean onKeyDown(int keyCode, KeyEvent event)
{
    if(event.getAction() == KeyEvent.ACTION_DOWN){
        switch(keyCode){
            case KeyEvent.KEYCODE_DEL:
            case KeyEvent.KEYCODE_FORWARD_DEL:
                return mConnection.deleteSurroundingText(0, 0);
            case KeyEvent.KEYCODE_ENTER:
                return mConnection.commitText("\n", 0);
        }
    }
    return super.onKeyDown(keyCode, event);
}

这样,编辑功能就OK了.

设定游标

输入必须得涉及到游标.
如何判断手指下的游标位置呢?只要简单measure一下就行了!
先写EventHandler:

@Override
public boolean onSingleTapConfirmed(MotionEvent e) {
    mEditor.showSoftInput();
    mScroller.forceFinished(true);
    int line = mEditor.getPointLineOnScreen(e.getY());
    int column = mEditor.getPointColumnOnScreen(line,e.getX());
    mEditor.setSelection(line,column);
    mEditor.hideAutoCompletePanel();
    return true;
}

然后是在View中实现:

/**
 * Get y position in scroll bounds's line's line
 * @param yPos Y in scroll bounds
 * @return line
 */
public int getPointLine(float yPos){
    int r = (int)yPos / getLineHeight();
    return r < 0 ? 0 : r;
}

/**
 * Get Y position on screen's line
 * @param y Y on screen
 * @return Line
 */
public int getPointLineOnScreen(float y){
    return Math.min(getPointLine(y + getOffsetY()),getLineCount() - 1);
}

/**
 * Get column in line for offset x
 * @param line Line
 * @param x Offset x
 * @return Column in line
 */
public int getPointColumn(int line, float x){
    if(x < 0){
        return 0;
    }
    if(line >= getLineCount()) {
        line = getLineCount() - 1;
    }
    float w = 0;
    int i = 0;
    prepareLine(line);
    while(w < x && i < mText.getColumnCount(line)){
        w += measureText(mChars, i, 1);
        i++;
    }
    if(w < x){
        i = mText.getColumnCount(line);
    }
    return i;
}

/**
 * Get column for x offset on screen
 * @param line Line
 * @param x X offset on screen
 * @return Column in line
 */
public int getPointColumnOnScreen(int line, float x){
    float xx = x + getOffsetX() - mDividerMargin * 2 - mDividerWidth - measureLineNumber();
    return getPointColumn(line, xx);
}

小结

至此,编辑框的基础功能已经好了,高亮功能稍后在做.由于10-11月的CSP非专业级考试就要来了,所以暂时停止更新.

高亮文本

从CSP差一分得省一的我回来了,依旧没有认真学习算法和数据结构的念头,反倒是继续更新编辑框了.

绘制Spans

我们把Span定义成一个只有开始位置和颜色的标记,List中下一个Span的开始位置,就是现在这个Span的结束位置,并且最后一个Span的结束位置是文末.
这样,就可以保证整篇文章都是被Span覆盖,可以方便地寻找位置.

public class Span {

    public int startIndex,line,column;
    public int colorId;

    /**
     * Create a span with brief position
     * @param i Index
     * @param l Line
     * @param c Column
     * @param cid Color ID
     */
    public Span(int i, int l, int c, int cid){
        colorId = cid;
        startIndex = i;
        line = l;
        column = c;
    }

    /**
     * Make self zero
     * @return self
     */
    public Span wrap(){
        line = column = 0;
        return this;
    }

    /**
     * Calculate line and column
     * @param c Target content
     * @return self
     */
    public Span wrap(Content c){
        CharPosition pos = c.getIndexer().getCharPosition(startIndex);
        line = pos.line;
        column = pos.column;
        return this;
    }

    /**
     * Create a new span from the given start index and color ID
     * @param start The start index
     * @param colorId Type of span
     */
    public Span(int start, int colorId){
        startIndex = start;
        this.colorId = colorId;
    }

    /**
     * Get span start line
     * @return Start line
     */
    public int getLine(){
        return line;
    }

    /**
     * Get span start column
     * @return Start column
     */
    public int getColumn(){
        return column;
    }
}

然后开始绘制!首先,由于我们是按行绘制,所以我们需要找到每一行行首对应需要绘制的Span,我们定义seekTo()方法:

private int seekTo(List<Span> spans, int line,int curr){
    while(curr < spans.size()) {
        Span span = spans.get(curr);
        if(span.getLine() < line && curr + 1 < spans.size() && (spans.get(curr + 1).getLine() < line||(spans.get(curr + 1).getLine() == line && spans.get(curr + 1).getColumn() == 0))){
            curr++;
        }else{
            break;
        }
    }
    return curr;
}

然后我们就可以绘制了:
我们的策略是按Span绘制一系列文本,而不是一个一个字符绘制,每绘制完一行,就重新开始绘制下一行.
不可见的区域不会被绘制.
IndexOutOfBoundsException的出现是因为改变了文本内容,相应的位置发生了变化,所以超出了范围,这时我们调用前面编写的drawTextDirect()方法绘制,来弥补这一错误,并且停止通过本方法绘制.

private void drawTextBySpans(Canvas canvas, float offsetX, TextColorProvider.TextColors colors){
    mPaint.setTypeface(mTypefaceText);
    ColorScheme cs = mColors;
    List<Span> spans = colors.getSpans();
    int first = getFirstVisibleLine();
    int last = getLastVisibleLine();
    int index = 0,copy;
    for(int i = first;i <= last;i++){
        index = seekTo(spans, i, index);
        copy = index;
        float off = offsetX;
        prepareLine(i);
        float y = getLineBaseLine(i) - getOffsetY();
        try{
            while(true){
                Span span = spans.get(copy),next = null;
                if(copy + 1 < spans.size()){
                    next = spans.get(copy + 1);
                }
                int st = span.getLine() == i ? span.getColumn() : 0;
                int ed = next == null ? mText.getColumnCount(i) : (next.getLine() == i ? next.getColumn() : mText.getColumnCount(i));
                float width = measureText(mChars, st, ed - st);
                if(off + width > 0 && off < getWidth()) {
                    mPaint.setColor(cs.getColor(span.colorId));
                    drawText(canvas, mChars, st, ed - st, off, y);
                }
                off += width;
                if(off - offsetX > mMaxPaintX){
                    mMaxPaintX = off - offsetX;
                }
                if(next == null || next.getLine() != i){
                    break;
                }
                copy++;
            }
        }catch(IndexOutOfBoundsException e){
            drawTextDirect(canvas, offsetX, mColors.getColor(ColorScheme.TEXT_NORMAL), i);
            break;
        }
    }
}

然后我们再写一个类用于绘制测试:

public class TestA implements Analyzer {

    @Override
    public void analyze(Content content, TextColorProvider.TextColors colors, TextColorProvider.AnalyzeThread.Delegate delegate) {
        colors.addIfNeeded(0, ColorScheme.CURRENT_LINE,content);
        colors.addIfNeeded(3,ColorScheme.SELECTION_HANDLE,content);
        colors.addIfNeeded(10,ColorScheme.LINE_DIVIDER,content);
    }

}

测试通过.
然后,本项目再一次被抛弃了一个月(2019/12~2020/01期间)

词法分析器

本来我是不打算继续更新编辑器了的,因为想到高亮代码的分析就觉得麻烦,烦躁.
不过,可喜的是寒假再一次地来到了.每当这个时候Rose总是要写一些好东西出来,今年也一样.
虽然今年寒假开头就给我补了5天课让我很不爽,不过幸好补课不用上晚自习.于是在晚上我就上网扯淡了.
想到暑假为新生的S5droid写了不少东西,也晓得了JFLex这个东西,我想了一下:每一次更新关键字都必须要改flex重新生成,真鸡儿麻烦,反正闲着也是没事干,我为什么不尝试手写一个词法分析器看看?
于是,词法分析器就开坑了.

定义单词

我们定义枚举类型Tokens:

public enum Tokens {
    //空白符号类 Whitespaces
    WHITESPACE,
    NEWLINE,
    UNKNOWN,
    EOF,

    //注释类 Comments
    LONG_COMMENT,//长注释 Long comment
    LINE_COMMENT,//单行注释 Single line comment

    DIV,//除
    MULT,//乘
    IDENTIFIER,//标识符
    INTEGER_LITERAL,//整数
    DOT,//点
    MINUS,//减
    STRING,//字符串
    CHARACTER_LITERAL,//字符
    LPAREN,//左小括号
    RPAREN,//右小括号
    LBRACE,//左大括号
    RBRACE,//右大括号
    LBRACK,//左中括号
    RBRACK,//右中括号
    SEMICOLON,//分号
    COMMA,//逗号
    EQ,//等于
    GT,//大于
    LT,//小于
    NOT,//非
    COMP,//~
    QUESTION,//问号
    COLON,//冒号
    AND,//与
    OR,//或
    PLUS,//加
    XOR,//异或
    MOD,//百分号
    DIVEQ,
    MULTEQ,
    FLOATING_POINT_LITERAL,//浮点数
    MINUSMINUS,//减减
    MINUSEQ,
    EQEQ,//等于等于
    GTEQ,
    RSHIFT,//右位移
    LTEQ,
    LSHIFT,//左位移
    NOTEQ,
    ANDEQ,
    ANDAND,//与与
    OREQ,
    OROR,//或或
    PLUSEQ,
    PLUSPLUS,//加加
    XOREQ,
    MODEQ,
    RSHIFTEQ,
    URSHIFT,
    LSHIFTEQ,
    URSHIFTEQ,

    //关键字
    FORLOOP,//变量循环
    WHILELOOP,//判断循环
    LONGV,//长整数型
    DOUBLEV,//双精度型
    FLOATV,//浮点数型
    BOOLEANV,//逻辑型
    INTV,//整数型
    STRINGV,//文本型
    OBJECT,//对象
    VARIANT,//变量
    ELSE,//否则
    IF,//如果
    STATIC,//静态
    CASE,//分支
    SWITCH,//判断
    LOOP,//循环
    METHOD,//方法
    EVENT,//事件
    END,//结束
    RETURN,//返回
    NEW,//创建
    NULL,//空
    FALSE,//假
    TRUE,//真
    TO,//至
    THEN,//则
    AS,//为
    ANDK,//与
    ORK,//或
    ELSEIF,//否则如果
    FORWARD,//步进
    BACK,//步退
    TRY,//容错处理
    CATCH,//捕获
    SIMPLE_TRY,//容错
    THIS,//本对象
    ASSERT,//断言
    BREAK,//跳出
    CONTINUE,//跳过
    INSTANCEOF,//从属于
    CHARV,//字节型
}

别吐槽字节型为什么是CHARV,不是我命的名啊…
到今天它已经多了两个新成员:类/继承,这里没加(懒)

分析

单词的构成都是有约束条件的.我们可以稍加分析:
空白符：诸如Tab、空格、垂直制表符
换行：\r\n或\n或\r
长度不为1的运算符:只需要向后逐字判断即可
数字:包括基本的十进制,以0打头的8进制,以0x或0X打头的16进制
字符常量:以’开头,以’结束,中间可以是一个字符或者一个转义的字符(\u….)
字符串常量:可以包括很多字符/转义字符
标识符:第一个字符属于IdentifierStart,后面部分属于IdentifierPart
关键字:和标识符具有相同的特征,本质是一个标识符,所以我们可以在扫描出一个标识符的时候测试它是否是一个关键字

具体实现

只需要一堆switch和if就可以实现了.为了方便,我们直接采用CharSequence作为操作对象,而不使用Reader了:

   public Tokens nextToken() {
       Tokens token;
       do {
           token = directNextToken();
       } while ((skipWS && token == WHITESPACE) || (skipComment && (token == LINE_COMMENT || token == LONG_COMMENT)));
       currToken = token;
       return token;
   }

   public Tokens directNextToken() {
       if (lcCal) {
           boolean r = false;
           for (int i = offset; i < offset + length; i++) {
               char ch = charAt(i);
               if (ch == '\r') {
                   r = true;
                   line++;
                   column = 0;
               } else if (ch == '\n') {
                   if (r) {
                       r = false;
                       continue;
                   }
                   line++;
                   column = 0;
               } else {
                   r = false;
                   column++;
               }
           }
       }
       index = index + length;
       offset = offset + length;
       if (offset == bufferLen) {
           return EOF;
       }
       char ch = source.charAt(offset);
       length = 1;
       if (ch == '\n') {
           return NEWLINE;
       } else if (ch == '\r') {
           scanNewline();
           return NEWLINE;
       } else if (isWhitespace(ch)) {
           char chLocal;
           while (offset + length < bufferLen && isWhitespace(chLocal = charAt(offset + length)) ) {
               if (chLocal == '\r' || chLocal == '\n') {
                   break;
               }
               length++;
           }
           return WHITESPACE;
       } else {
           if (isIdentifierStart(ch)) {
               return scanIdentifier(ch);
           }
           if (isPrimeDigit(ch)) {
               return scanNumber();
           }
           /* Scan usual symbols first */
           if(ch == ';') {
               return SEMICOLON;
           }else if(ch == '(') {
               return LPAREN;
           }else if(ch == ')') {
               return RPAREN;
           }else if(ch == ':') {
               return COLON;
           }else if(ch == '<') {
               return scanLT();
           }else if(ch == '>') {
               return scanGT();
           }
           /* Scan secondly symbols */
           switch (ch) {
               case '=':
                   return scanOperatorTwo('=', EQ, EQEQ);
               case '.':
                   return DOT;
               case '{':
                   return LBRACE;
               case '}':
                   return RBRACE;
               case '/':
                   return scanDIV();
               case '*':
                   return scanOperatorTwo('=', MULT, MULTEQ);
               case '-':
                   return scanOperatorTwo('=', '-', MINUS, MINUSEQ, MINUSMINUS);
               case '+':
                   return scanOperatorTwo('=', '+', PLUS, PLUSEQ, PLUSPLUS);
               case '[':
                   return LBRACK;
               case ']':
                   return RBRACK;
               case ',':
                   return COMMA;
               case '!':
                   return NOT;
               case '~':
                   return COMP;
               case '?':
                   return QUESTION;
               case '&':
                   return scanOperatorTwo('&', '=', AND, ANDAND, ANDEQ);
               case '|':
                   return scanOperatorTwo('|', '=', OR, OROR, OREQ);
               case '^':
                   return scanOperatorTwo('=', XOR, XOREQ);
               case '%':
                   return scanOperatorTwo('=', MOD, MODEQ);
               case '\'':
                   scanCharLiteral();
                   return CHARACTER_LITERAL;
               case '\"':
                   scanStringLiteral();
                   return STRING;
               default:
                   error("没有匹配的Token : '" + ch + " '", new StringAdvice("检查是否使用了非法的符号，比如误使用了中文符号代替英文符号等"));
                   return UNKNOWN;
           }
       }
   }
protected Tokens scanOperatorTwo(char ex1, char ex2, Tokens ifWrong, Tokens ifRight1, Tokens ifRight2);
   protected Tokens scanOperatorTwo(char expected, Tokens ifWrong, Tokens ifRight);

二级方法略,其中isIdentifierStart()和isIdentifierPart()直接调用Character的isJavaIdentifierStart()和isJavaIdentifierPart()方法
至于关键字,我们只需要用一个HashMap<String,Tokens>就可以实现操作了.
成功识别出词法.

优化

在上面的过程后,我们虽然分析出了词法,可是和JFLex比起来却慢得多,这令人疑惑不解.
我们注意到了这个方法的实现:

1
2
3

public String getTokenString() {
    return source.subSequence(offset, offset + length).toString();
}

每次我们识别标识符的时候都必须利用这个方法得到Token的内容,只这一下调用,我们就必须创建2个新对象!
而我们写程序的时候,往往标识符是很多的,所以我们自然就慢了!
我们希望有一个方法,不需要创建对象,就可以识别出它是不是个标识符,而复杂度和HashMap一样!
这个时候,我们想起了TrieTree.
TrieTree实际上就是一颗树,它的每个字符都是一个节点,节点依据输入字符串的顺序连接,最终节点标记为tail.
如果我们hash一下的话,那么获取相应叶节点的复杂度均摊是O(1),我们一般需要操作n次,所以折合应该是O(n),而且因为关键字很稀少,我们往往查找到一半甚至还在根节点就无结果返回了,这又节约了不少时间.
这样一来n的系数又变小了,所以效率很高.
我们于是写出了TrieTree的实现:

public class TrieTree<T> {

    public Node<T> root;
    private int maxLen;

    public TrieTree() {
        root = new Node<>();
        maxLen = 0;
    }

    public void put(String v,T token) {
        maxLen = Math.max(v.length(),maxLen);
        addInternal(root,v,0,v.length(),token);
    }

    public void put(CharSequence v,int off,int len,T token) {
        maxLen = Math.max(maxLen,len);
        addInternal(root,v,off,len,token);
    }

    public T get(CharSequence s,int offset,int len) {
        if(len > maxLen) {
            return null;
        }
        return getInternal(root,s,offset,len);
    }

    private T getInternal(Node<T> node,CharSequence s,int offset,int len) {
        if(len == 0) {
            return node.token;
        }
        char point = s.charAt(offset);
        Node<T> sub = node.map.get(point);
        if(sub == null) {
            return null;
        }
        return getInternal(sub, s, offset + 1, len - 1);
    }

    private void addInternal(Node<T> node,CharSequence v,int i,int len,T token) {
        char point = v.charAt(i);
        Node<T> sub = node.map.get(point);
        if(sub == null) {
            sub = new Node<>();
            node.map.put(point, sub);
        }
        if(len == 1) {
            sub.token = token;
        }else {
            addInternal(sub, v, i + 1,len - 1, token);
        }
    }

    public static class Node<T> {

        public HashCharMap<Node<T>> map;

        public T token;

        public Node() {
            this.map = new HashCharMap<>();
        }

    }

    /**
     * 固定长度哈希表
     * @author Rose
     */
    public static class HashCharMap<V> {

        private LinkedPair<V>[] columns;

        private LinkedPair<V>[] ends;

        private final static int CAPACITY = 64;

        @SuppressWarnings("unchecked")
        public HashCharMap() {
            columns = new LinkedPair[CAPACITY];
            ends = new LinkedPair[CAPACITY];
        }


        private static int position(int first) {
            return Math.abs(first ^ (first << 6) * ((first & 1) != 0 ? 3 : 1)) % CAPACITY;
        }

        public V get(char first) {
            int position = position(first);
            LinkedPair<V> pair = columns[position];
            while(pair != null) {
                if(pair.first == first) {
                    return pair.second;
                }
                pair = pair.next;
            }
            return null;
        }

        private LinkedPair<V> get(char first,int position) {
            LinkedPair<V> pair = columns[position];
            while(pair != null) {
                if(pair.first == first) {
                    return pair;
                }
                pair = pair.next;
            }
            return null;
        }

        public void put(char first, V second) {
            int position = position(first);
            if(ends[position] == null) {
                columns[position] = ends[position] = new LinkedPair<>();
                ends[position].first = first;
                ends[position].second = second;
                return;
            }
            LinkedPair<V> p = get(first, position);
            if(p == null) {
                p = ends[position].next = new LinkedPair<>();
                ends[position] = p;
            }
            p.first = first;
            p.second = second;
        }


    }

    /**
     * 数据节点
     * @author Rose
     */
    public static class LinkedPair<V>{

        public LinkedPair<V> next;

        public char first;

        public V second;

    }

}

修改scanIdentifier():

protected Tokens scanIdentifier(char ch) {
    TrieTree.Node<Tokens> n = keywords.root.map.get(ch);
    while (offset + length < bufferLen && isIdentifierPart(ch = charAt(offset + length))) {
        length++;
        n = n == null ? null : n.map.get(ch);
    }
    return n == null ? IDENTIFIER : (n.token == null ? IDENTIFIER : n.token);
}

但是重新运行,我们发现效率高了不少,但是还是差JFLex不少,这是为什么呢?
这时,我别无推卸,只能认定自己的方法不行吗?
不.
这是,我们看向了用于识别标识符的两个方法.
我们用循环测试一下:

long start = System.currentMillis();
for(int i = 0;i < str.length();i++) {
    Character.isIdenrifierPart(str.charAt(i));
}
System.out.println(System.currentMillis() - start);
start = System.currentMillis();
for(int i = 0;i < str.length();i++) {
    Character.isIdenrifierStart(str.charAt(i));
}
System.out.println(System.currentMillis() - start);
start = System.currentMillis();
for(int i = 0;i < str.length();i++) {
    str.charAt(i);
    str.charAt(i);
}
System.out.println(System.currentMillis() - start);

结果发现:调用了Character的两个循环比不调用的时间多得多!
于是我们编写了自己测试是否标识符的方法,由于失败(很慢)了,这里不给出了.
编写的方法用的是一堆’||’连接来判断,比自带的慢得多.
我们猜想:Character的这两个方法的内部实现很有可能在native层,而且很有可能也是这样一堆’||’,所以很慢,但是比在Java中实现快.
于是我们采用空间换时间的办法再优化:

public class MyCharacter {

    public static boolean[] state1,state2;
    public static boolean[] state3,state4;
    
    public static void initMap() {
        if(state1 != null) {
            return;
        }
        
        state1 = new boolean[35000];
        state2 = new boolean[65536 - 35000];
        for(int i = 0;i < 35000;i++) {
            state1[i] = Character.isJavaIdentifierPart((char)i);
        }
        for(int i = 35000;i <= 65535;i++) {
            state2[i - 35000] = Character.isJavaIdentifierPart((char)i);
        }
        
        state3 = new boolean[35000];
        state4 = new boolean[65536 - 35000];
        for(int i = 0;i < 35000;i++) {
            state3[i] = Character.isJavaIdentifierStart((char)i);
        }
        for(int i = 35000;i <= 65535;i++) {
            state4[i - 35000] = Character.isJavaIdentifierStart((char)i);
        }
    }
    
    public static boolean isJavaIdentifierPart(int key) {
        if(key < 35000) {
            return state1[key];
        }else {
            return state2[key - 35000];
        }
    }
    
    public static boolean isJavaIdentifierStart(int key) {
        if(key < 35000) {
            return state3[key];
        }else {
            return state4[key - 35000];
        }
    }
}

使用之前记得调用initMap()
我们在实际应用时想到:boolean只能保存一个状态却占用1字节空间,但是换成int就可以4个字节保存32个状态,大大压缩了空间
于是利用位运算,我们又写出了:

public class MyCharacter {
    
    private static int[] state_start;

    private static int[] state_part;

    private static boolean get(int[] values,int bitIndex) {
        return ((values[bitIndex / 32] & (1 << (bitIndex % 32))) != 0);
    }

    private static void set(int[] values,int bitIndex) {
        values[bitIndex / 32] |= (1 << (bitIndex % 32));
    }

    public static void initMap() {
        if(state_start != null) {
            return;
        }
        state_part = new int[2048];
        state_start = new int[2048];
        Arrays.fill(state_part,0);
        Arrays.fill(state_start,0);
        for(int i = 0;i <= 65535;i++) {
            if(Character.isJavaIdentifierPart((char) i)) {
                set(state_part,i);
            }
            if(Character.isJavaIdentifierStart((char) i)) {
                set(state_start,i);
            }
        }
    }

    public static boolean isJavaIdentifierPart(int key) {
        return get(state_part,key);
    }
    
    public static boolean isJavaIdentifierStart(int key) {
        return get(state_start,key);
    }
}

这样就把空间压缩到了原来的1/8.
而词法分析器的速度更是大大提高,居然远超JFLex.

升级Android部分

就在我在各个QQ群里面水吹我的词法分析器时,有人开始催我更新编辑器了.
我已经在QQ群里面吹过多次我要写个高亮编辑器了,每一次都是半途而废,这一次他们戏称我”写了一年了”(因为上次提出要写编辑器已经是在上个寒假了)
我想了一想,写就写!反正之前已经完成了很多工作了,只是加个高亮而已,有什么好怕的!
加上此时新型冠状病毒肆虐,假期延长的通知发来了,第二期的补课取消已经是板上钉钉的事情了,怕个屁!直接开搞!
于是我又启动了凤凰OS.

高亮分析

初步

只需要操作Tokenizer即可.
针对每一个Token添加对于的Span到List就好了
(Line,Column,Index)可以直接从Tokenizer/Content获取

Span加速

分析:我们添加Span,没有必要每个Token都添加.
因为我们并不是相邻的Token一定是不同的颜色.例如:多个关键字连接在一起
而且,WHITESPACE和NEWLINE我们根本不需要为之添加Span–他们根本看不见.
这样一来,我们定义了方法addSpanIfNeeded(),只在需要时添加Span,以免浪费内存空间,而且需要更多时间(List不断扩容)
这也可以加速绘制.

charAt()加速

由于词法分析几乎是流式地获取char,我们启用CachedIndexer加快速度.
AnalyzeThread中的段落:

1 2	Content copy = content.makeCopy(); copy.beginStreamCharGetting(0);

然后写出了S5droidColorProvider,实现Analyzer.
但是发现分析速度很慢,为什么呢?
把一切添加Span的操作注释,运行发现还是很慢,证明是charAt出了问题.
查看CachedIndexer,发现每次charAt都会造成新对象的产生,这就有问题了!
我们于是使得它在词法分析时只使用一个对象返回结果,果然快了不少,但是还是达不到我们理想的状态:20w在1s内分析完.
现在使用了大约3s.
于是我们更换LexIndexer:

public class LexIndexer implements Indexer
{
    private CharPosition pos;
    private Content content;
    private int line,column,index;
    private int linecount;
    
    public LexIndexer(Content content){
        this.content = content;
        index = line = column = 0;
        pos = new CharPosition();
        linecount = content.getColumnCount(0);
    }
    
    //Don't need
    @Override
    public int getCharIndex(int line, int column)
    {
        return 0;
    }
    
    //Don't need
    @Override
    public int getCharLine(int index)
    {
        return 0;
    }

    //Don't need
    @Override
    public int getCharColumn(int index)
    {
        return 0;
    }
    
    private void forward() {
        index++;
        column++;
        if(column == linecount + 1) {
            line++;
            column = 0;
            linecount = content.getColumnCount(line);
        }
    }
    
    private void backward() {
        index--;
        if(column == 0) {
            line--;
            linecount = column = content.getColumnCount(line);
        }else{
            column--;
        }
    }

    @Override
    public CharPosition getCharPosition(int index0)
    {
        while(index < index0) forward();
        while(index > index0) backward();
        pos.column = column;
        pos.line = line;
        pos.index = index0;
        return pos;
    }

    //Don't need
    @Override
    public CharPosition getCharPosition(int line, int column)
    {
        return null;
    }
}

果然,时间降下到2s左右了.
还是达不到我们的要求.
此时需要另辟蹊径.
我们尝试直接把Content给转换成一个StringBuilder(不toString())了,然后直接操作这个StringBuilder对象,至于(Line,Column)的计算我们交给辅助类LineNumberHelper来做:

public class LineNumberHelper
{
    private CharSequence mTarget;
    private int mOffset;
    private int mLine;
    private int mColumn;
    private int mLength;
    
    public LineNumberHelper(CharSequence target) {
        mTarget = target;
        mOffset = mLine = mColumn = 0;
        mLength = mTarget.length();
    }
    
    public void update(int length) {
        for(int i = 0;i < length;i++) {
            if(mOffset + i == mLength) {
                break;
            }
            if(mTarget.charAt(mOffset + i) == '\n') {
                mLine++;
                mColumn = 0;
            }else{
                mColumn++;
            }
        }
        mOffset = mOffset + length;
    }
    
    public int findLineStart() {
        return mOffset - mColumn;
    }
    
    public int findLineEnd() {
        int i = 0;
        for(;i + mOffset < mLength;i++) {
            if(mTarget.charAt(mOffset + i) == '\n') {
                break;
            }
        }
        return mOffset + i;
    }
    
    public int getLine() {
        return mLine;
    }
    
    public int getColumn() {
        return mColumn;
    }
    
}

这是我们惊喜地发现,时间降到800ms左右了!
而且纯词法分析也只有200ms!

绘制加速 - 二分法的应用

我们在上面的Span寻址中,使用的是顺序查找的方法,顺序查找的时间复杂度是O(N).在我们Span比较少的时候可以很快地找到地址,但是如果我们的Span很多的时候((比如用户滑动到20万行),这个时候第一次寻找地址的时间就会很长.
经过测试,每行大约5个Span时,滑动到20w行之后,绘制时间大约在20ms,这显然远远高出了16ms的要求.这时我们就要请出我们的好朋友二分法(Binary Search)了.
Binary Search是编程中常用的算法之一.必须在 ** 数据有序 ** 的时候使用.而Span的排列顺序显然服从这个规律(词法分析是从前向后的,所以Span的起始位置一定是服从从小到大排列的顺序的)
所以,如果我们在第一次寻址的时候使用二分法,后面接着前面查找出的结果使用顺序查找法,寻址速度可以大大提高.
于是,我们对seekTo()函数稍加修改.

   /**
    * Find for the start of line in spans
    * @param spans Spans
    * @param line Searching line
    * @return Start span index in spans
    */
   private int binarySearch(List<Span> spans, int line) {
       int left = 0,right = spans.size() - 1,mid,row;
       int max = right;
       while(left <= right){
           mid = (left + right) / 2;
           if(mid < 0) return 0;
           if(mid > max) return max;
           row = spans.get(mid).getLine();
           if(row == line) {
               return mid;
           }else if(row < line){
               left = mid + 1;
           }else{
               right = mid - 1;
           }
       }
       return Math.max(0,Math.min(left,max));
   }

/**
    * Find the first span for line by binary search
    * @param spans Spans
    * @param line Searching line
    * @return First span index
    */
   private int seekTo(List<Span> spans, int line){
       int curr = binarySearch(spans,line);
       if(curr >= spans.size()){
           curr = spans.size() - 1;
       }else if(curr < 0){
           curr = 0;
       }
       while(curr > 0){
           Span span = spans.get(curr);
           if(span.getLine() >= line){
               curr--;
           }else{
               break;
           }
       }
       while(true) {
           Span span = spans.get(curr);
           if(span.getLine() < line && curr + 1 < spans.size() && (spans.get(curr + 1).getLine() < line||(spans.get(curr + 1).getLine() == line && spans.get(curr + 1).getColumn() == 0)) ) {
               curr++;
           }else{
               break;
           }
       }
       return Math.min(curr,spans.size() - 1);
   }

   /**
    * Find first span for the given line
    * @param spans Spans
    * @param line Searching line
    * @param curr Current index
    * @return New position
    */
   private int seekTo(List<Span> spans, int line,int curr){
       if(curr == 0){
           return seekTo(spans,line);
       }
       while(curr < spans.size()) {
           Span span = spans.get(curr);
           if(span.getLine() < line && curr + 1 < spans.size() && (spans.get(curr + 1).getLine() < line||(spans.get(curr + 1).getLine() == line && spans.get(curr + 1).getColumn() == 0))){
               curr++;
           }else{
               break;
           }
       }
       return curr;
   }

为了保证结果的正确,这里用了两个while循环.
如果** 你 **觉得不用也可以去掉.
我们惊喜地发现,绘制速度已经下降到3-4ms了!
特别提示:代码区划线的绘制只有末尾符合二分法的要求,开头的Index不是严格递增的!!!

结语

编辑框大致到这里就已经完成了,后面的工作是代码补全和代码区划线,也很简单.
同样是利用二分法加速了代码区划线的绘制,以及一个SuppressSwitch上限来控制寻找上限(这是由代码块的性质决定的).
自动补全只需要生成一颗代码块树就能实现了,然后递归操作即可,这里也不多讲了.
关键是我们在构建编辑框的同时,对二分法的应用以及数据结构TrieTree的应用有了更多更广的认识,这对于我们的开发是很有帮助的.