javascriptでCSVのparser/stringifierを書いてみた

# javascriptでCSVのparser/stringifierを書いてみた

## 目的

CSVのライブラリをさがしてみたが、わりと大規模なものであったり
小さくても思ったようにparse出来なかったりした。
コピペで動きそこそこ正確なものが欲しかったので作ってみた。

## 想定しているCSV

RFC4180で定義されたものに加え、以下のようなケースもサポートする。
区切り記号はカンマ(\x2C)、改行記号はCR(\x0D),LF(\x0A),CRLF(\x0D\x0A)に対応する。

### ケース1. 項目の先頭以外のダブルクォートをエラーとしない

```js
parse('aaa,b"bb,ccc'); //=> [['aaa', 'b"bb', 'ccc]]
```

### ケース2. ダブルクォートが閉じていない場合、文末までを1項目とする

```js
parse('A,B,"C\nD,E,F'); //=> [['A', 'B', 'C\nD,E,F']]
```

### ケース3. その他

```js
// 空白やnullは [] に変換する
parse(''); //=> []

// 文末の改行を無視する実装もあるようだが、ここでは律儀に処理する
parse('a,b,c\n'); //=> [['a', 'b', 'c'], []]

// #で始まる行をコメントとする実装もあるようだが、考慮しない
parse('#comments\na,b,c'); //=> [['#comments'], ['a', 'b', 'c']
```

## 実装

### stringifierの実装

parserに比べ、stringifierは単純である。以下のように実装した。
1項目を文字列化するescape関数も同時に作成している。

```js
var CSV = {};
CSV.escape = function(val) {
	if (val===null||val===undefined) {return "";}
	if (/[",\r\n]/.test(val)) { //",\r\nが含まれる場合はenquoteする
		val = '"' + val.replace(/"/g, '""') + '"';
	}
	return val;
};
CSV.stringifier = function(rows) {
	var str = "", i, il, j, jl;
	for(i=0,il=rows.length; i<il; i++) {
		for(j=0,jl=rows[i].length; j<jl; j++) {
			str += CSV.escape(rows[i][j]) + (j+1===jl ? '' : ',');
		}
		str += "\n";
	}
	return str.replace(/\n$/,'');
};

```

### parserの実装

何通りかの実装方法を考えた。
まず、単純に1文字ずつ読みとり配列を更新してゆく方法。

```js
CSV.parse1 = function(str) {
	var rows = [], row = [], i, len, v, s = "", q, c;
	for(i=0,len=str.length; i<len; i++) {
		v = str.charAt(i);
		if (q) { //quoted
			if (v === '"') { //quotを発見
				if (str.charAt(i+1) === '"') { //次もquotならバッファに1つだけ足す
					i++;
					s += v;
				} else {                       //そうでないならnot quotedへ
					q = false;
				}
			} else {         //quot以外はバッファに追加
				s += v;
			}
		} else { //not quoted
			if (v === '"' && !s) {    //quotでバッファが空ならquotedへ
				q = true;
			} else if (v === ',') {   //カンマならバッファをrowに追加しバッファを空に
				row.push(s); s = "";
			} else if (v === '\r' || v === '\n') {  //改行ならバッファをrowに追加し、rowsにrowを追加し、rowとバッファを空に
				row.push(s); s = "";
				rows.push(row); row = [];
				if (v === '\r' && str.charAt(i+1) === '\n') {i++;}
			} else {                  //それ以外はバッファに追加
				s += v;
			}
		}
	}
	if (s || v === ',' || !s && v === '"') {row.push(s);}
	if (row.length) {rows.push(row);}
	if (!s && (v === '\r' || v === '\n')) {rows.push([]);} //最後の改行を無視する場合はコメントアウト
	return rows;
};
```

わかりやすいが効率は悪そうだ。

次に、注意すべきはダブルクォート・カンマ・改行だけなのだから `String.prototype.indexOf` でそれらの位置だけ調べればよい。以下のように実装した

```js
CSV.parse2 = function(str) {
	var i, c, r, q, l, m, v, j, len=str.length, rows = [], row = [];
	for(i=0,l="\n",v=len,c=["\r\n","\r","\n"];i<3;i++) {if (~(j=str.indexOf(c[i]))&&j<v) {l=c[i];v=j;}} //\r\n,\r,\nのうち最初に出現したものを改行記号とする
    m = l.length;
	for(i=0,c=r=-1; i<len; i++) {
		if (str.charAt(i) === '"') { //quoted
			for(j=0,q=i+1; q<len; j++,q++) { //閉quotを探す
				q = (q=str.indexOf('"',q)) < 0 ? len+1 : q; //quotの位置、無いなら末尾まで
				if (str.charAt(++q) !== '"') {break;}       //""なら継続
			}
			row.push((v=str.substring(i+1,(i=q)-1),j) ? v.replace(/""/g,'"') : v);
		} else { //not quoted
			if (c<i) {c=str.indexOf(',',i);c=c<0?len:c;} //直近のカンマ位置と
			if (r<i) {r=str.indexOf(l,i);r=r<0?len:r;}   //直近の改行位置を調べ
			row.push(str.substring(i,(i=c<r?c:r)));      //そこまでを値とする
		}
		if (i === r || l === (m>1?str.substr(i,m):str.charAt(i))) {rows.push(row);row=[];i+=m-1;}
	}
	str.charAt(i-1) === ',' && row.push(''); //,で終わる
	row.length && rows.push(row);
	str.substr(i-1,m) === l && rows.push([]); //最後の改行を無視する場合はコメントアウト
	return rows;
};
```

最後に、正規表現による実装。

```js
CSV.parse3 = (function(re) {
	if (!re) {re = new RegExp('"(?:[^"]|"")*"|"(?:[^"]|"")*$|[^,\r\n]+|\r?\n|\r|,+', 'g');}
	return function(l) {
		var c, m, n, r = [['']];
		if (!l) {return [];}
		//l = l.replace(/\r?\n|\r$/,''); //最後の改行を無視する場合
		while(m = re.exec(l)) {
			if ((c = m[0].charAt(0)) === ',') {for(c=m[0].length; c>0; c--) {r[r.length-1].push('');}continue;}
			if (c === '\n' || c === '\r\n' || c === '\r') {r.push(['']);continue;}
			(n=r[r.length-1])[n.length-1] = c === '"' ? m[0].replace(/^"|"$/g,'').replace(/""/g,'"') : m[0];
		}
		return r;
	};
}());
```

やはり正規表現が一番短く書けた。
ちなみに`String.prototype.replace`や`String.prototype.match`でも書けるが`RegExp.prototype.exec`の方が早いようだ。

## 比較

上記 parse1,2,3 及び PapaParse( http://papaparse.com/ )、続・正規表現を使ったCSVパーサ( http://liosk.blog103.fc2.com/blog-entry-75.html )との比較してみた。

実験に使ったのは手元にあった3MB程度のCSV(ダブルクォートがたまに出現する)で、50回parseした経過時間の平均値で比べる。

結果は

1. parse2 (indexOfによる実装)  39.5ms
2. PapaParse  58.5ms
3. parse3 (正規表現による実装) 72.6ms
4. 続・正規表現を使ったCSVパーサ 92.5ms
5. parse1 (1文字ずつ読みとり) 150.5ms

環境やparseするデータにもよるであろうから参考程度に。

## 考察

そこそこ短いCSV parser/stringifier は実現できたと思う。
また、よくある正規表現による実装は余り早くないことがわかった。
ただ、より巨大なCSVを扱う場合はcallback関数を渡すなどの工夫が必要であろう。
そう考えると小さいCSVしか扱わないなら、2倍程度遅い正規表現でも問題ではないのかもしれない。

## 付録

より短く記述したものを貼り付けておく

```tinycsv.js
(function(g) {
'use strict';
var C = {};

/**
 * CSVをparseする
 * 入力文字列を1文字ずつ調べている
 * @param {String} str CSV形式の文字列
 * @return {Array} 2重配列
 */
C.charParse = function(str) {
	var rows = [], row = [], i, len, v, s = "", q, c;
	for(i=0,len=str.length; i<len; i++) {
		s = (v=str.charAt(i),q) ? v === '"' ? (q = str.charAt(i+1) === '"') ? (i++,s+v) : s : s+v :
				(q = v === '"' && !s) ? s : v === ',' ? (row.push(s),'') : 
				v === '\r' || v === '\n' ? (row.push(s),rows.push(row),row=[],v==='\r'&&str.charAt(i+1)==='\n'&&i++,'') : s+v
	}
	if (s || v === ',' || !s && v === '"') {row.push(s);}
	if (row.length) {rows.push(row);}
	if (!s && (v === '\r' || v === '\n')) {rows.push([]);}
	return rows;
};

/**
 * カンマ、改行記号、ダブルクォートの位置から配列を作る
 */
C.idxParse = function(str) {
	var i, c, r, q, l, m, v, j, len=str.length, rows = [], row = [];
	for(i=0,l="\n",v=len,c=["\r\n","\r","\n"];i<3;i++) {if (~(j=str.indexOf(c[i]))&&j<v) {l=c[i];v=j;}} //\r\n,\r,\nのうち最初に出現したものを改行記号とする
    m = l.length;
	for(i=0,c=r=-1; i<len; i++) {
		if (str.charAt(i) === '"') { //quoted
			for(j=0,q=i+1; (q=(q=str.indexOf('"',q))<0?len+1:q)<len&&str.charAt(++q)==='"'; j++,q++) {}
			row.push((v=str.substring(i+1,(i=q)-1),j) ? C.deq(v) : v);
		} else { //not quoted
			if (c<i) {c=str.indexOf(',',i);c=c<0?len:c;}
			if (r<i) {r=str.indexOf(l,i);r=r<0?len:r;}
			row.push(str.substring(i,(i=c<r?c:r)));
		}
		if (i === r || l === (m>1?str.substr(i,m):str.charAt(i))) {rows.push(row);row=[];i+=m-1;}
	}
	str.charAt(i-1) === ',' && row.push('');
	row.length && rows.push(row);
	str.substr(i-1,m) === l && rows.push([]);
	return rows;
};
/**
 * 正規表現によるparse
 */
C.regexParse = (function(re) {
	if (!re) {re = new RegExp('"(?:[^"]|"")*"|"(?:[^"]|"")*$|[^,\r\n]+|,+|\r?\n|\r', 'gm');}
	return function(l) {
		var c, m, n, r = [['']];
		if (!l) {return [];}
		while(m = re.exec(l)) {
			if ((c = m[0].charAt(0)) === ',') {for(c=m[0].length; c>0; c--) {r[r.length-1].push('');}continue;}
			if (c === '\n' || c === '\r\n' || c === '\r') {r.push(['']);continue;}
			(n=r[r.length-1])[n.length-1] = c === '"' ? C.deq(m[0], true) : m[0];
		}
		return r;
	};
}());

/**
 * ダブルクォート2つを1つに置換する関数
 * str.replace(/""/g, '"')の代わりに使うと多少早いかもしれない
 * @param {String}       s  入力文字列
 * @param {Boolean|null} p  先頭と末尾のダブルクォートを削除する場合はtrue。defaultは削除しない
 * @return {String} ダブルクォートを置換した文字列
 */
C.deq = function(s, p, o, i, l) {
	if (p) {s=s.charAt(0)==='"'?s.slice(1,s.charAt(l=s.length-1)==='"'?l:l+1):s;}
	for(i=0,o='',l=s.length; o+=(p=s.indexOf('""',i))<0?s.slice(l=i):s.substring(i,i=p+1),i<l; i++) {}
	return o;
};

C.escape = function(val) {
	if (val===null||val===undefined) {return "";}
	if (/[",\r\n]/.test(val)) {val = '"' + val.replace(/"/g, '""') + '"';}
	return val;
};

C.unescape = function(val) {return !val ? '' : C.deq(val, true);};

C.stringify = function(rows) {
	var str = "", i, il, j, jl;
	for(i=0,il=rows.length; i<il; i++) {
		for(j=0,jl=rows[i].length; j<jl; j++) {
			str += C.escape(rows[i][j]) + (j+1===jl ? '' : ',');
		}
		str += "\n";
	}
	return str.replace(/\n$/,'');
};

C.parse = C.idxParse;

g.TinyCSV=(g.window?{}:module).exports=C;

}(this));
```