Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 12415] ファイルの概要

このコミットは、Go言語のstrconvパッケージに、文字が印字可能（printable）であるかを判定するためのテーブルベースのisPrint関数とその生成ツールを追加するものです。具体的には、以下の3つのファイルが変更されています。

  • src/pkg/strconv/isprint.go: 新規追加されたファイルで、印字可能なUnicodeコードポイントの範囲と例外を定義するテーブルが含まれています。このファイルは手動で編集されるものではなく、makeisprint.goによって自動生成されます。
  • src/pkg/strconv/makeisprint.go: 新規追加されたファイルで、isprint.goを生成するためのGoプログラムです。unicodeパッケージのIsPrint関数を利用して、印字可能な文字の範囲を計算し、効率的なルックアップテーブルとして出力します。
  • src/pkg/strconv/quote.go: 既存のファイルで、isPrint関数とそれに関連するバイナリサーチ関数（bsearch16, bsearch32）が追加されています。コミットメッセージには「Not used yet for simpler merge.」とありますが、このコミットでisPrint関数がquote.go内に定義され、将来的に利用される準備がされています。

コミット

commit e9d5a641d7c6c5d446c158f90249167133d5ccee
Author: Russ Cox <rsc@golang.org>
Date:   Tue Mar 6 00:36:12 2012 -0500

    strconv: add table-based isPrint
    
    Not used yet for simpler merge.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/5756048

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/e9d5a641d7c6c5d446c158f90249167133d5ccee

元コミット内容

strconv: add table-based isPrint

Not used yet for simpler merge.

変更の背景

このコミットの主な目的は、Go言語のstrconvパッケージにおいて、Unicode文字が「印字可能」であるかを効率的に判定するメカニズムを導入することです。コミットメッセージにある「Not used yet for simpler merge.」という記述は、このisPrint関数がすぐにstrconvパッケージ内の既存の機能（例えば、文字列のリテラル化やクォート処理）で利用されるわけではないが、将来的な統合を容易にするために、まずテーブルと生成ロジックを導入したことを示唆しています。

Go言語では、文字列はUTF-8でエンコードされたバイト列として扱われ、個々の文字はrune型（Unicodeコードポイントを表すint32のエイリアス）で表現されます。文字列処理において、特定の文字が画面に表示されるべき「印字可能」な文字であるかどうかの判定は、セキュリティ上の理由（制御文字の除去など）や、表示の整形（引用符で囲む際のエスケープ処理など）のために重要となります。

以前のstrconv.IsPrintの実装は、unicode.IsPrintに依存していたと考えられます。unicode.IsPrintは、Unicodeの文字プロパティに基づいて印字可能性を判定しますが、これは一般的に広範なUnicodeデータテーブルを内部的に参照するため、パフォーマンスが懸念される場合があります。特に、頻繁に呼び出される可能性のあるstrconvパッケージのような低レベルな場所では、より高速な判定メカニズムが求められます。

このコミットは、unicode.IsPrintのロジックを基にしつつも、strconvパッケージ内で最適化されたテーブルルックアップ方式を導入することで、パフォーマンスの向上を図ることを意図しています。自動生成されるテーブルを使用することで、Unicodeの更新にも対応しやすくなります。

前提知識の解説

Go言語のrune型とUnicode

Go言語において、文字列はUTF-8でエンコードされたバイト列として扱われます。個々の文字はrune型で表現され、これは実質的にint32のエイリアスであり、Unicodeのコードポイント（文字を一意に識別する番号）を表します。これにより、Goは多言語対応を容易にしています。

strconvパッケージ

strconvパッケージは、Go言語の標準ライブラリの一部であり、基本的なデータ型（整数、浮動小数点数、真偽値など）と文字列との間の変換機能を提供します。例えば、Atoi（文字列を整数に変換）、Itoa（整数を文字列に変換）、Quote（文字列をGoのリテラル形式で引用符で囲む）などの関数があります。このパッケージは、文字列のパースやフォーマットにおいて非常に頻繁に利用されます。

unicodeパッケージ

unicodeパッケージは、Go言語の標準ライブラリの一部であり、Unicodeの文字プロパティに関する機能を提供します。これには、文字が数字であるか、文字であるか、空白であるか、あるいは印字可能であるかなどを判定する関数が含まれます。

  • unicode.IsPrint(r rune) bool: この関数は、与えられたruneがGoの定義する「印字可能」な文字であるかどうかを報告します。Goにおける印字可能な文字とは、文字、記号、数字、句読点、そしてASCIIスペース（U+0020）を指します。これには、改行、タブ、制御文字などの非印字文字は含まれません。

印字可能な文字 (Printable Characters)

「印字可能な文字」とは、通常、画面に表示されたり、紙に印刷されたりする際に視覚的な表現を持つ文字を指します。これには、アルファベット、数字、記号、句読点などが含まれます。対照的に、改行、タブ、バックスペース、NULL文字などの「制御文字」は、通常、視覚的な表現を持たず、特定の動作を制御するために使用されます。プログラミングにおいては、文字列処理や出力において、印字可能な文字と非印字可能な文字を区別することが重要になります。

ルックアップテーブル (Lookup Table)

ルックアップテーブルは、特定の入力値に対応する出力値を事前に計算して格納しておくデータ構造です。これにより、実行時に複雑な計算を繰り返す代わりに、テーブルから直接結果を取得できるため、処理速度を向上させることができます。文字のプロパティ判定においては、特定の文字コードが持つプロパティ（例: 印字可能かどうか）を、文字コードをインデックスとしてテーブルから参照することで、高速な判定が可能になります。

バイナリサーチ（二分探索）は、ソートされた配列から特定の要素を探し出すための効率的なアルゴリズムです。探索範囲を半分ずつに絞り込んでいくため、要素数Nに対してO(log N)の計算量で動作します。このコミットでは、印字可能な文字の範囲や例外文字のリストがソートされた状態でテーブルに格納されており、特定のruneがその範囲に含まれるか、または例外リストに含まれるかを判定するためにバイナリサーチが利用されています。

技術的詳細

このコミットで導入されたisPrintの実装は、Unicodeのコードポイントを効率的に分類するために、事前に計算されたルックアップテーブルとバイナリサーチを組み合わせたものです。

テーブル構造

isprint.goファイルには、以下の4つのuint16またはuint32のスライス（配列）が定義されています。

  • isPrint16: 0x0000から0xFFFFまでの範囲（つまりuint16で表現できる範囲）の印字可能な文字の範囲を格納します。各範囲は[開始コードポイント, 終了コードポイント]のペアで表現されます。例えば、0x0020, 0x007eはASCIIスペースからチルダまでの範囲を示します。
  • isNotPrint16: 0x0000から0xFFFFまでの範囲で、isPrint16の範囲に含まれるが、実際には印字可能ではない例外的な文字のコードポイントを格納します。
  • isPrint32: 0x10000からunicode.MaxRuneまでの範囲（つまりuint32で表現する必要がある範囲）の印字可能な文字の範囲を格納します。構造はisPrint16と同様です。
  • isNotPrint32: 0x10000からunicode.MaxRuneまでの範囲で、isPrint32の範囲に含まれるが、実際には印字可能ではない例外的な文字のコードポイントを格納します。

これらのテーブルは、makeisprint.goによって自動生成されます。makeisprint.goは、unicode.IsPrint関数を呼び出して各Unicodeコードポイントの印字可能性をチェックし、その結果に基づいて効率的な範囲と例外のリストを作成します。

isPrint関数のロジック

quote.goに追加されたisPrint(r rune) bool関数は、以下のロジックで動作します。

  1. runeの範囲判定:

    • 入力されたrune rが0以上かつ1<<16（つまり65536）未満の場合、そのruneはuint16で表現できる範囲にあると判断されます。この場合、isPrint16とisNotPrint16テーブルが使用されます。
    • それ以外の場合、runeはuint32で表現する必要がある範囲にあると判断され、isPrint32とisNotPrint32テーブルが使用されます。

  2. 印字可能範囲のチェック:

    • 選択されたisPrintテーブル（isPrint16またはisPrint32）に対して、入力rune rr（uint16またはuint32にキャストされたもの）をbsearch16またはbsearch32関数でバイナリサーチします。
    • bsearch関数は、rr以上の最初の要素のインデックスiを返します。
    • このインデックスiと、その前後の要素（isPrint[i&^1]とisPrint[i|1]）を使って、rrが印字可能範囲[isPrint[i&^1], isPrint[i|1]]に含まれるかどうかをチェックします。
      • i&^1はiを偶数に切り捨てるビット演算で、範囲の開始コードポイントを指します。
      • i|1はiを奇数に切り上げるビット演算で、範囲の終了コードポイントを指します。
    • もしrrがどの印字可能範囲にも含まれない場合、falseを返します。

  3. 例外リストのチェック:

    • rrが印字可能範囲に含まれると判断された場合、次に選択されたisNotPrintテーブル（isNotPrint16またはisNotPrint32）に対して、rrをbsearch関数でバイナリサーチします。
    • bsearch関数は、rr以上の最初の要素のインデックスjを返します。
    • もしisNotPrint[j]がrrと等しい場合、そのruneは例外リストに含まれるため、実際には印字可能ではないと判断され、falseを返します。
    • 例外リストに含まれない場合、そのruneは印字可能であると判断され、trueを返します。

bsearch16 / bsearch32関数

これらの関数は、ソートされたuint16またはuint32のスライスaの中から、与えられた値x以上の最小の要素のインデックスを返すバイナリサーチの実装です。もしそのような要素が存在しない場合、スライスの長さ（len(a)）を返します。

makeisprint.goの役割

makeisprint.goは、isprint.goを生成するためのツールです。

  • scan(min, max rune)関数は、指定されたminからmaxまでのruneの範囲を走査し、unicode.IsPrintの結果に基づいて印字可能な文字の範囲（rang）と例外文字（except）を収集します。
  • to16(x []uint32)関数は、uint32のスライスをuint16のスライスに変換します。
  • main関数では、0から0xFFFFまでの範囲と、0x10000からunicode.MaxRuneまでの範囲でscanを実行し、それぞれisPrint16, isNotPrint16, isPrint32, isNotPrint32の各テーブルを生成し、isprint.goの形式で標準出力に出力します。これにより、isprint.goは常に最新のUnicodeプロパティに基づいて生成されることが保証されます。

このテーブルベースのアプローチは、unicodeパッケージが提供する汎用的なIsPrint関数よりも、特定のstrconvのユースケースにおいて高速な判定を可能にすることを目的としています。

コアとなるコードの変更箇所

src/pkg/strconv/isprint.go (新規追加)

このファイルは、makeisprint.goによって自動生成されるため、手動での編集は推奨されません。 内容は、isPrint16, isNotPrint16, isPrint32, isNotPrint32という4つのuint16またはuint32のスライス定義です。これらは、印字可能な文字の範囲と、その範囲内にあるが印字可能ではない例外文字のリストをそれぞれ格納しています。

例:

// DO NOT EDIT.  GENERATED BY
//     go run makeisprint.go >x && mv x isprint.go

package strconv

var isPrint16 = []uint16{
	0x0020, 0x007e, // ASCII Space to Tilde
	// ... 多数の範囲定義 ...
}

var isNotPrint16 = []uint16{
	0x00ad, // Soft Hyphen
	// ... 多数の例外文字定義 ...
}

var isPrint32 = []uint32{
	0x000020, 0x00007e,
	// ... 多数の範囲定義 ...
}

var isNotPrint32 = []uint32{
	0x1000c,
	// ... 多数の例外文字定義 ...
}

src/pkg/strconv/makeisprint.go (新規追加)

このファイルは、isprint.goを生成するためのGoプログラムです。 unicodeパッケージをインポートし、unicode.IsPrint関数を使用して印字可能な文字の範囲を特定します。 bsearch16, bsearch32関数は、生成されたテーブルのテストのために一時的に含まれていますが、最終的なisprint.goには含まれません。 scan関数がUnicodeの全範囲を走査し、印字可能な文字の範囲と例外を収集します。 main関数がこれらの情報を整形し、isprint.goの形式で標準出力に出力します。

// Copyright 2012 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// +build ignore

// makeisprint generates the tables for strconv's compact isPrint.
package main

import (
	"fmt"
	"unicode"
)

// ... bsearch16, bsearch32, isPrint (テスト用) 関数定義 ...

func scan(min, max rune) (rang, except []uint32) {
	// minからmaxまでのruneを走査し、unicode.IsPrintの結果に基づいて範囲と例外を収集
}

func to16(x []uint32) []uint16 {
	// uint32スライスをuint16スライスに変換
}

func main() {
	// isPrint16, isNotPrint16, isPrint32, isNotPrint32 の各テーブルを生成
	// 生成されたテーブルをGoのコードとして標準出力に出力
}

src/pkg/strconv/quote.go (変更)

このファイルには、isPrint関数と、その内部で利用されるbsearch16およびbsearch32関数が追加されています。これらの関数は、isprint.goで定義されたテーブルを参照して印字可能性を判定します。

// ... 既存のコード ...

// bsearch16 returns the smallest i such that a[i] >= x.
// If there is no such i, bsearch16 returns len(a).
func bsearch16(a []uint16, x uint16) int {
	i, j := 0, len(a)
	for i < j {
		h := i + (j-i)/2
		if a[h] < x {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

// bsearch32 returns the smallest i such that a[i] >= x.
// If there is no such i, bsearch32 returns len(a).
func bsearch32(a []uint32, x uint32) int {
	i, j := 0, len(a)
	for i < j {
		h := i + (j-i)/2
		if a[h] < x {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

func isPrint(r rune) bool {
	// Same algorithm, either on uint16 or uint32 value.
	// First, find first i such that isPrint[i] >= x.
	// This is the index of either the start or end of a pair that might span x.
	// The start is even (isPrint[i&^1]) and the end is odd (isPrint[i|1]).
	// If we find x in a range, make sure x is not in isNotPrint list.

	if 0 <= r && r < 1<<16 {
		rr, isPrint, isNotPrint := uint16(r), isPrint16, isNotPrint16
		i := bsearch16(isPrint, rr)
		if i >= len(isPrint) || rr < isPrint[i&^1] || isPrint[i|1] < rr {
			return false
		}
		j := bsearch16(isNotPrint, rr)
		return j >= len(isNotPrint) || isNotPrint[j] != rr
	}

	rr, isPrint, isNotPrint := uint32(r), isPrint32, isNotPrint32
	i := bsearch32(isPrint, rr)
	if i >= len(isPrint) || rr < isPrint[i&^1] || isPrint[i|1] < rr {
		return false
	}
	j := bsearch32(isNotPrint, rr)
	return j >= len(isNotPrint) || isNotPrint[j] != rr
}

コアとなるコードの解説

このコミットの核心は、strconvパッケージにおけるisPrint関数の実装を、動的な判定から静的なルックアップテーブルに基づく判定へと移行させる点にあります。

isprint.go

このファイルは、makeisprint.goによって生成されるデータファイルです。Goのソースコードとして、印字可能な文字の範囲と例外文字のリストをuint16とuint32の配列として定義しています。これらの配列は、Unicodeの全コードポイントを網羅的にチェックするのではなく、印字可能な文字が連続する「範囲」と、その範囲内にあるが印字可能ではない「例外」を効率的に表現しています。これにより、メモリ使用量を抑えつつ、高速なルックアップを可能にしています。

makeisprint.go

このプログラムは、isprint.goを生成する「ジェネレータ」です。unicodeパッケージのIsPrint関数を呼び出すことで、Go言語が定義する印字可能性の基準に従って、各Unicodeコードポイントの印字可能性を判定します。そして、その結果を基に、isprint.goで使われるisPrint16, isNotPrint16, isPrint32, isNotPrint32の各テーブルを構築します。この自動生成プロセスにより、Unicodeの新しいバージョンがリリースされた際にも、makeisprint.goを再実行するだけでisprint.goを簡単に更新でき、メンテナンス性が向上します。

quote.go内のisPrint関数とbsearch関数

quote.goに追加されたisPrint関数は、実際に文字の印字可能性を判定するロジックを実装しています。この関数は、入力されたruneがuint16の範囲かuint32の範囲かによって、使用するテーブル（isPrint16/isNotPrint16またはisPrint32/isNotPrint32）を切り替えます。

判定ロジックは以下のステップで行われます。

  1. 範囲の特定: bsearch関数（bsearch16またはbsearch32）を使用して、入力runeが印字可能な文字の範囲を定義するテーブル（isPrint16またはisPrint32）内のどの範囲に属するかを効率的に特定します。bsearchはソートされた配列に対して二分探索を行うため、非常に高速です。
  2. 範囲内チェック: bsearchで得られたインデックスと、そのインデックスが指す範囲の開始・終了コードポイントを使って、入力runeがその範囲内に実際に含まれるかを確認します。
  3. 例外チェック: もし入力runeが印字可能範囲に含まれる場合、次にisNotPrintテーブル（isNotPrint16またはisNotPrint32）に対して再度bsearchを実行し、入力runeが印字可能ではない例外文字のリストに含まれていないかを確認します。

この二段階のチェックとテーブルベースのルックアップ、そしてバイナリサーチの組み合わせにより、isPrint関数は非常に効率的に動作し、strconvパッケージのパフォーマンス向上に貢献します。コミットメッセージにある「Not used yet for simpler merge.」は、このisPrint関数がまだquote.go内の他の関数から直接呼び出されていないことを示していますが、将来的にstrconv.Quoteなどの関数で、文字列を引用符で囲む際にどの文字をエスケープすべきかを判断するために利用されることが想定されます。

関連リンク

参考にした情報源リンク