背景

いま、Goでテキストエディタを趣味で作っていて、バッファ操作の設計と実装を行っている。
バッファは基本的に配列ではなくGoのsliceで実装しているので、バッファ操作≒slice操作となる。
なんとくなくで実装してたら、案の定ハマりまくった。

そこで、一通りsliceの挙動と操作について学習してみた。
今回はその学習の評価を行うためにミニマルなラインエディタを試作し、slice操作が意図通り行えるか確認してみた。(vimの祖先であるexエディタのノリを再現してみたいという好奇心もあった。)

※ 完全に自分のための振り返りなので、やや記事として粗雑ですがご了承ください。

ズバッと実装してみた物体

ラインエディタは、幾つかの古典的なスクリーンテキストエディタの前身ともなっているテキストエディタ。
基本的には、読み込んだテキストの行を移動し、その行へテキストの挿入や削除を行って編集を行うもの。

というわけで、インタラクティブシェルのイメージで、コマンド+引数でコマンド実行して編集するように実装してみた。

実装したコマンド
- out
  - 編集中のバッファの内容を出力する
- line
  - 編集中の行番号を出力する
- mov
  - 編集する行を変更する
- ins
  - 挿入位置と挿入する文字列を指定し、行へ文字列を挿入する
- del
  - 削除する先頭位置と削除する文字数を指定し、行も文字列を削除する
- save
  - 編集中のバッファをout.txtの名前でファイルへ出力する
- quit
  - プログラムを終了する

bash-3.2$ ./slice_practice sample.txt 
Cmd>out
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
Cmd>mov 2
Cmd>line
2
Cmd>del 0 4
Cmd>out
0123456789
0123456789
456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
Cmd>ind 0 Hoge
Cmd>command not found
Cmd>ins 0 Hoge
Cmd>out
0123456789
0123456789
Hoge456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
Cmd>save
Cmd>quit
bash-3.2$ ls
out.txt         sample.txt      slice_practice      slice_practice.go
bash-3.2$ cat out.txt 
0123456789
0123456789
Hoge456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
bash-3.2$

コマンドの中でinsとdelでslice操作を行っているので、次はその具体的な操作を示す。

とりあえずのソースコード

slice_practice.go

package main

import (
    "bufio"
    "fmt"
    "gopkg.in/alecthomas/kingpin.v2"
    "io/ioutil"
    "log"
    "os"
    "strconv"
)

type File struct {
    lines   []string
    lineNum uint
}

type Command struct {
    command string
    arg1    uint
    arg2    string
}

const ()

var (
    fileptr = kingpin.Arg("file", "Editing filename").Required().File()

    file File
    cmd  Command
)

func main() {

    err := Init()
    if err != nil {
        log.Fatal(err)
    }

    // Intaractive routine
mainloop:
    for {
        fmt.Printf("Cmd>")
        fmt.Scanf("%s%d%s", &cmd.command, &cmd.arg1, &cmd.arg2)

        switch cmd.command {
        case "out":
            file.OutBuf()
        case "line":
            file.DispLineNum()
        case "mov":
            file.MoveLine(cmd.arg1)
        case "ins":
            file.InsertStr(cmd.arg1, cmd.arg2)
        case "del":
            file.DeleteStr(cmd.arg1, cmd.arg2)
        case "save":
            file.SaveBuf()
        case "quit":
            break mainloop
        default:
            fmt.Println("command not found")
        }
        cmd.ClearCmd()
    }

}

func Init() error {
    kingpin.Parse()
    defer func() {
        (*fileptr).Close()
    }()

    scanner := bufio.NewScanner(*fileptr)
    for scanner.Scan() {
        file.lines = append(file.lines, scanner.Text())
    }
    if err := scanner.Err(); err != nil {
        return err
    }

    file.lineNum = 0
    return nil
}

func (f *File) MoveLine(line uint) {
    if int(line) > len(file.lines) {
        fmt.Println("out of range")
        return
    }
    f.lineNum = line
}

func (f *File) DispLineNum() {
    fmt.Println(file.lineNum)
}

func (file *File) InsertStr(pos uint, exp string) {
    if int(pos) > len(file.lines[file.lineNum]) {
        fmt.Println("out of range")
        return
    }

    buf := []byte(file.lines[file.lineNum])
    ptr := pos
    str := exp
    for _, c := range []byte(str) {
        // 挿入のためのslice操作
        buf = append(buf, 0)
        copy(buf[ptr+1:], buf[ptr:])
        buf[ptr] = c
        ptr++
    }
    file.lines[file.lineNum] = string(buf)
}

func (file *File) DeleteStr(pos uint, delnum string) {
    num, _ := strconv.Atoi(delnum)
    if int(pos)+num > len(file.lines[file.lineNum]) {
        fmt.Println("out of range")
        return
    }
    pos++
    // 削除のためのslice操作
    buf := []byte(file.lines[file.lineNum])
    buf = append(buf[:pos-1], buf[pos+uint(num)-1:]...)
    file.lines[file.lineNum] = string(buf)
}

func (f *File) OutBuf() {
    for _, line := range f.lines {
        fmt.Println(line)
    }
}

func (f *File) SaveBuf() {
    var content []byte
    for _, line := range f.lines {
        for _, c := range []byte(line) {
            content = append(content, c)
        }
        content = append(content, byte('\n'))
    }
    ioutil.WriteFile("out.txt", content, os.ModePerm)
}

func (c *Command) ClearCmd() {
    c.command = ""
    c.arg1 = 0
    c.arg2 = ""
}

sliceの任意の位置への挿入と、任意の範囲の削除(本題)

前章までは手遊びの垂れ流し。
ここからが本題。

そもそもsliceって??
- Goでは配列とは別に用意されているデータ型
- 配列が固定長なのに対して、sliceは可変長
- sliceは、全体を指すポインタと、長さ、容量を持つ
- Goでは配列に代わって多くの場合でsliceが使用される
最も基本的なslice操作
部分参照は以下のようにできる。

参照方法	解説
a[:]	全要素
a[2:]	2番目から最後まで
a[:5]	初めから(5-1)番目まで
a[3:5]	3番目から(5-1)番目まで

要素の追加は組み込み関数append()にて行う。
slice = append(slice, element1, element2...)

スライスのコピーは組み込み関数copy()にて行う。
copy(a, b) // スライスaにbをコピー

ある程度Goの基本的な言語仕様をおさえていれば、スライスの自由な操作は以上の操作の組み合わせにて行える。

今回の実装

挿入

func (file *File) InsertStr(pos uint, exp string) {
    if int(pos) > len(file.lines[file.lineNum]) {
        fmt.Println("out of range")
        return
    }

    buf := []byte(file.lines[file.lineNum])
    ptr := pos
    str := exp
    for _, c := range []byte(str) {
        // 挿入のためのslice操作
        buf = append(buf, 0)
        copy(buf[ptr+1:], buf[ptr:])
        buf[ptr] = c
        ptr++
    }
    file.lines[file.lineNum] = string(buf)
}

// 挿入のためのスライス操作以下3行がsliceへの挿入処理
- buf = append(buf, 0)で、挿入先のsliceの長さを1要素分延長する
- copy(buf[ptr+1:], buf[ptr:])で、挿入位置(ptr)+1の位置へ、挿入位置(ptr)より後の要素をコピー
  - 処理後は挿入位置(ptr)の要素は空のまま、元の要素がその前後に格納された状態となる
- buf[ptr] = cで、挿入位置(ptr)へ、要素を挿入する

削除

func (file *File) DeleteStr(pos uint, delnum string) {
    num, _ := strconv.Atoi(delnum)
    if int(pos)+num > len(file.lines[file.lineNum]) {
        fmt.Println("out of range")
        return
    }
    pos++
    buf := []byte(file.lines[file.lineNum])
    // 削除のためのslice操作
    buf = append(buf[:pos-1], buf[pos+uint(num)-1:]...)
    file.lines[file.lineNum] = string(buf)
}

// 削除のためのslice操作以下1行がsliceへの削除処理
- buf = append(buf[:pos-1], buf[pos+uint(num)-1:]...)で、削除位置(pos)までのsliceへ、削除位置+削除数(num)-1から最後までのsliceを追加する
  - 処理後は、削除位置(pos)を含み削除数(num)の数だけの要素を除いたsliceがbufへ代入される

まとめ・TODO

まとめ
- 他の言語では、配列やスライスのようなデータ型への操作関数(Perlでいうshiftやunshit、popなど)が存在する場合が多いがGoには存在しない
  - ある程度ユーザが定義する必要があるので、しっかりsliceの動作を理解しなければならない
- その反面、ユーザがデータ構造への操作を定義できるので、パフォーマンスにこだわった設計が可能
TODO
- パフォーマンスを考えると、append()や、copy()を使用すべきではないという意見もあり、実測値でもそういったデータが存在する
  - 上記の組み込み関数を使用しないslice操作も検討し実装できる必要がある

参考

slice操作については、以下のドキュメント(Goのgithub wiki)へ詳しく書かれているので、参考になった。

SliceTricks(Go github wiki)

Goのslice操作の復習としてラインエディタを試作

背景

ズバッと実装してみた物体

とりあえずのソースコード

sliceの任意の位置への挿入と、任意の範囲の削除(本題)

まとめ・TODO

参考