Edited at

JavaScript で JVM (Java Virtual Machine) を実装する (Hello World 出力編)


背景

先日、Builderscon tokyo 2019 で PHP で JVM を実装して Hello World を出力するまで という内容で登壇しました。

仕組み上、 PHP 以外の言語でももちろん実装できるというお話をさせていただいて、じゃぁ本当にできるのか?ということで JavaScript でも実装してみました。一発ネタです。

Screen Shot 2019-09-01 at 13.09.34.png

PHPerKaigi 2019 では PHP でクラスファイルの読み方についてというトークをしています。


実装していく

実装は至ってシンプルで中間コードのクラスファイル (例: Test.class) を FileReader で読み込んで 1 文字ずつ処理をしていくだけです。

PHP に標準で備わってる StreamWrapper や unpack を使用せず、ビット演算したりしています。


class ファイルを JavaScript で読み込めるようにする

アップロードされたファイルを読み込むにはおなじみの FileReader クラスを使います。

document.addEventListener('DOMContentLoaded', (e) => {

document.querySelector('#file').addEventListener('change', (e) => {
const files = e.target.files;
for (const file of files) {
const reader = new FileReader();
reader.onload = (e) => {
(new Analyzer(
new Uint8Array(e.target.result),
document)
).analyze();
};
reader.readAsArrayBuffer(file);
}
})
});

読み込み時は readAsArrayBuffer を使い、配列として扱えるようにします。かつ、それを Uint8Array として符号なし (1 つの要素が 0 から 255 の範囲)の配列にしたものを、class ファイルを解析するための Analyzer クラスに渡します。


使うコードは下記の通り

みんなおなじみの Hello World です。

class HelloWorld {

public static void main(String[] args) {
System.out.println("Hello World!")
}
}


Class File Structure を読み込んでいく


  • Class File Structure は JVM Spec より下記のとおりです。

ClassFile {

u4 magic;
u2 minor_version;
u2 major_version;
u2 constant_pool_count;
cp_info constant_pool[constant_pool_count-1];
u2 access_flags;
u2 this_class;
u2 super_class;
u2 interfaces_count;
u2 interfaces[interfaces_count];
u2 fields_count;
field_info fields[fields_count];
u2 methods_count;
method_info methods[methods_count];
u2 attributes_count;
attribute_info attributes[attributes_count];
}

u2byte が 2 つあるものです。ほとんどは unsigned short として扱われるので、ここでは unsigned short として紹介します。

u4 も同様ですが 4 桁なので unsigned int として扱います。


unsigned short の計算方法

2 バイト (8 bit + 8 bit) を読み込みます。 Uint8Array なので slice をします。

ビッグエンディアンなので左から 0, 1, ... のように読み込みます。リトルエンディアンの場合は逆です。

const readUnsignedShort = () => {

const bytes = source.slice(this.pos, this.pos + 2);
this.pos += 2;
return bytes[0] << 8 | bytes[1];
}

これで unsigned short の値が算出できます。 ここでは出てきませんが、符号付きの場合は 0x7fff 以下がポジティブな値で、 0x8000 以上がネガティブな値です。

ちなみになんで、これで計算ができるのかというと、例えば 275 という値の場合 16 bit で表すと下記のようになります。

0000 0001 0001 0011

1 バイトは 8 bit なので、 それぞれの要素には [0000 0001, 0001 0011] の値が格納されている、つまり 10 進数で表すと [1, 19] という要素が入っています。これら 1 バイトずつをもとに戻す作業のようなものです。

この 2 つを足す必要があります。言い換えると、 0000 0001 0001 0011 のような形に戻して上げる必要があります。

どうするかというと、0000 00010001 0011 分左に追いやる必要があります。ということで 8 bit 分左にシフトさせる必要があります。そして、 19 を足して上げる必要があります。

1 << 8 | 19

これはどうなっているかというと 1 << 8 の時点で、

0000 0001 0000 0000

左にシフトされ、移動した分は 0 で埋め尽くされます。そのあと、 19 である 0001 0011 を足します。

  0000 0001 0000 0000

+ 0000 0000 0001 0011
----------------------
0000 0001 0001 0011

そうすることで、 0000 0001 0001 0011 つまり、 275 となります。

ではなぜ、 | で足し算になるのかというと、ビットが立っていればそこはビットが立つからです。

つまり、左辺と右辺どちらかの値が 1 であれば、 1 となるということです。逆に & は両辺ともビットが立っていなければ 1 となりません。

<< でシフトした分の値は 0 で埋め尽くされているのは既知で、この性質を用いることにより足し算と同等になります。


unsigned int の計算方法

これも short と一緒で、桁が増えるだけです。

const readUnsignedInt = () => {

const bytes = source.slice(this.pos, this.pos + 4);
this.pos += 4;
return bytes[0] << 24
| bytes[1] << 16
| bytes[2] << 8
| bytes[3];
}

原理は上述の unsigned short と一緒です。


magicbyte を読み込む

magicbyte は class ファイルは一貫して CAFEBABE です。 10 進数で表すと 3405691582 です。

magicbyte 関連としては JPEG や PNG などといったバイナリにも埋め込まれています。

u4 で、つまり unsigned int としてここでは扱うので、下記のようになります。

const magicbytes = readUnsignedInt();

これで終了です。本来は値が正しいかどうかをチェックするべきだと思いますが、ここでは省略します。

他のものも同様に読み込んでいきます。


minor_version, major_version, constant_pool_count を読み込む

const minorVersion = readUnsignedShort();

const majorVersion = readUnsignedShort();
const cpCount = readUnsignedShort();


constant pool を読み込む

次に JVM の要である Constant Pool を読み込みます。 Hello World の出力では下記の 6 種類が必要です。


  • CONSTANT_Class

  • CONSTANT_Fieldref

  • CONSTANT_Methodref

  • CONSTANT_NameAndType

  • CONSTANT_String

  • CONSTANT_Utf8

これらは Tag として扱われていて、 Constant Pool のエントリの種類を表しています。

cp_info という構造は JVM Spec より下記のようになっています。

cp_info {

u1 tag;
u1 info[];
}

引用: https://docs.oracle.com/javase/specs/jvms/se11/html/jvms-4.html#jvms-4.4

info は Tag の種類によって読み込むものが異なっています。


  • CONSTANT_Class

CONSTANT_Class_info {

u1 tag;
u2 name_index;
}


  • CONSTANT_Fieldref

CONSTANT_Fieldref_info {

u1 tag;
u2 class_index;
u2 name_and_type_index;
}


  • CONSTANT_Methodref

CONSTANT_Methodref_info {

u1 tag;
u2 class_index;
u2 name_and_type_index;
}


  • CONSTANT_NameAndType


CONSTANT_NameAndType_info {
u1 tag;
u2 name_index;
u2 descriptor_index;
}


  • CONSTANT_String

CONSTANT_String_info {

u1 tag;
u2 string_index;
}


  • CONSTANT_Utf8

CONSTANT_Utf8_info {

u1 tag;
u2 length;
u1 bytes[length];
}

引用: https://docs.oracle.com/javase/specs/jvms/se11/html/jvms-4.html#jvms-4.4

これらの処理を JavaScript で書くと下記のようになるかと思います。また、 Constant Pool の index は 0 からスタートではなく、 1 からスタートという仕様のため、 0 番目には undefined を予め入れておきます。

const cp = [undefined];

for (let i = 1; i < cpCount; i++) {
const tag = read(1)[0];
switch (tag) {
case 0x07: // CONSTANT_Class
cp.push({
tag,
nameIndex: readUnsignedShort(),
});
break;
case 0x09: // CONSTANT_Fieldref
case 0x0A: // CONSTANT_Methodref
cp.push({
tag,
classIndex: readUnsignedShort(),
nameAndTypeIndex: readUnsignedShort(),
});
break;
case 0x08: // CONSTANT_String
cp.push({
tag,
stringIndex: readUnsignedShort(),
});
break;
case 0x0C: // CONSTANT_NameAndType
cp.push({
tag,
nameIndex: readUnsignedShort(),
descriptorIndex: readUnsignedShort(),
});
break;
case 0x01: // CONSTANT_Utf8
const utf8Obj = {
tag,
length: readUnsignedShort(),
};

utf8Obj.bytes = read(utf8Obj.length);
cp.push(utf8Obj);
break;
default:
throw new Error('Unknown Constant tag. ' + tag);
}
}

※ read は指定したバイト数を読み込んで、そのバイト数分 this.pos を増やすメソッドです。


access_flags, this_class, super_class, interfaces_count を読み込む

それぞれ u2 なので、 Class File Structure に従って読み込みます。

const accessFlags = readUnsignedShort();

const thisClass = readUnsignedShort();
const superClass = readUnsignedShort();
const interfacesClass = readUnsignedShort();


interfaces を読み込む

interfaces は実装されていないので 0 件です。特に何かしらする必要はないですが、気持ち的にループ文をおいておきます。

for (let i = 0; i < interfaceCount; i++) {

// お気持ちステートメント
}


fields_count, fields, methods_count を読み込む

これも Class File Structure に則り読み込みます。また、 fields は定義されていないので、 interfaces と同様にお気持ちステートメントだけおいておきます。

const fieldsCount = readUnsignedShort();

for (let i = 0; i < fieldsCount; i++) {
// お気持ちステートメント
}

const methodsCount = readUnsignedShort();


methods を読み込む

Hello World を中間コードへコンパイルすると 2つのメソッドが定義されます。 一つは今回のエントリーポイントである main ともう一つはコンストラクタである <init> です。Java は通常クラス名と同名のメソッドを定義して、コンストラクタとして扱われますが、 JVM における実態としては <init> でコンパイルされるようです。

したがって、 methodsCount には 2 件エントリがあり、それらを読み込む必要があります。

methods のエントリは JVM Spec により下記の構造として定義されています。

method_info {

u2 access_flags;
u2 name_index;
u2 descriptor_index;
u2 attributes_count;
attribute_info attributes[attributes_count];
}

引用: https://docs.oracle.com/javase/specs/jvms/se11/html/jvms-4.html#jvms-4.6

attribute は後ほど何回か登場する構造なので、ひとまとめにしておきます。

analyzeAttribute() {

const attributeNameIndex = readUnsignedShort();
const attributeLength = readUnsignedInt();

return {
attributeNameIndex,
attributeLength,
payload: read(attributeLength)
};
}

これを用いて method_info Structure に従い読み込んでいきます。

const methods = [];

for (let i = 0; i < methodsCount; i++) {
const obj = {
accessFlags: readUnsignedShort(),
nameIndex: readUnsignedShort(),
descriptorIndex: readUnsignedShort(),
attributesCount: readUnsignedShort(),
attributes: [],
};

for (let j = 0; j < obj.attributesCount; j++) {
obj.attributes.push(analyzeAttribute());
}

methods.push(obj);
}

これでメソッド部分は読み込めました。


attributes_count, attributes を読み込む。

クラスファイル自体の属性情報を読み込みます。

const attributesCount = readUnsignedShort();

const attributes = [];
for (let j = 0; j < attributesCount; j++) {
attributes.push(analyzeAttribute());
}

以上で Class File Structure の読み込みは終わりました。


Hello World を出力する

Hello World を出力する前に javap コマンドを用いて、 main メソッドがどういった処理をしているのかを見てみます。

... 省略

public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream;
3: ldc #3 // String Hello World!
5: invokevirtual #4 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
8: return
LineNumberTable:
line 5: 0
line 6: 8
... 省略

上記のようになっています。 Code: と書かれているところが実際の処理になります。 Hello World の出力には下記の 4 つの処理があります。


  • getstatic

  • ldc

  • invokevirtual

  • return

それぞれどういったことをしているのか、簡単に説明します。


getstatic

getstatic は 2 バイト分のオペランドを持ち、これは Constant Pool のインデックスを示しています。

この例だと #2 となっているので Constant Pool の 2 番目を指しています。

また、 2 バイト分のオペランドは unsigned short で表現できます。

取得した値はオペランドスタック (と呼ばれるメモリ上)に積まれます。


ldc

ldc は 1 バイト分のオペランドを持ち、これは Constant Pool のインデックスを示しています。

この例だと #3 となっているので Constant Pool の 3 番目を指しています。

また、 1 バイト分のオペランドは unsigned byte で表現できます。

こちらも取得した値はオペランドスタックに積まれます。


invokevirtual

invokevirtual は 2 バイト分のオペランドを持ち、これは Constant Pool のインデックスを示しています。

この例だと #4 となっているので Constant Pool の 4 番目を指しています。

この値はメソッド名と descriptor の情報が入っている CONSTANT_NameAndType になります。

また、オペランドスタックから descriptor で定義されている数だけ pop してきます。

そして、最後に一回だけ pop をします。これが呼び出し元のクラスの情報が入っている CONSTANT_Methodref になります。

そして、それらの情報を用いて実行をして、 descriptor の返却値が void 以外であればそれをオペランドスタックに積みます。

本来はもっといろんな機能が満載なんですが、 Hello World を出力するだけであれば、これで差し支えないかなと思います。


return

本来は後処理とか色々するんですが、 Hello World を出力するだけであれば、特に何もしません。


出力までの準備をする

先程の methods 変数にメソッドの情報が格納されています。 methods の構造は下記のとおりです。

{

accessFlags: short,
nameIndex: short,
descriptorIndex: short,
attributesCount: short,
attributes: array,
}

本当はシグネチャが正しいかどうかの検証も必要ですが、今回はメソッド名だけで判別します。

nameIndex は Constant Pool のインデックス値が入っており、これを使って呼び出したいメソッドを絞ります。

for (const method of methods) {

const methodName = (new TextDecoder()).decode(
Uint8Array.from(
cp[method.nameIndex].bytes
)
);

if (methodName !== 'main') {
continue;
}

// ...ここに main メソッドの処理を書いていく
}

また、method の attributes には CodeAttribute というものがあり、この属性がメソッドの実行、つまり ldcgetstatic などといったオペレーションを行うために必要なものとなります。

したがって、 attributes から CodeAttribute を下記のように絞る必要があります。

また、絞ったあとに CodeAttribute をついでに読みます。 CodeAttribute は JVM Spec より下記のとおりです。

Code_attribute {

u2 attribute_name_index;
u4 attribute_length;
u2 max_stack;
u2 max_locals;
u4 code_length;
u1 code[code_length];
u2 exception_table_length;
{ u2 start_pc;
u2 end_pc;
u2 handler_pc;
u2 catch_type;
} exception_table[exception_table_length];
u2 attributes_count;
attribute_info attributes[attributes_count];
}

上記を表すと下記のようになります。

for (const attribute of method.attributes) {

const attributeName = (new TextDecoder()).decode(
Uint8Array.from(
attribute.attributeNameIndex
)
);
if (attributeName !== 'Code') {
continue;
}
const stream = new BinaryStream(code)
const maxStack = stream.readUnsignedShort();
const maxLocals = stream.readUnsignedShort();
const codeLength = stream.readUnsignedInt();
const code = stream.read(codeLength);

const exceptionTableLength = stream.readUnsignedShort();

for (let i = 0; i < exceptionTableLength; i++) {
// お気持ちステートメント
}

const attributesCount = stream.readUnsignedShort();
const attributes = [];
for (let i = 0 ; i < attributesCount; i++) {
attributes.push(analyzeAttribute());
}

const operandStack = [];
const codeStream = new BinaryStream(code);

// ... ldc や getstatic などをここで処理していく
}
}

途中で登場してくる BinaryStreamUint8array を指定した型でスライスしていってくれるクラスです。


出力していく

あとは ldcgetstatic の処理を JVM Spec 見つつただ愚直に書いていくだけです。

とはいえ、 Hello World の出力で本格的に実装する必要もないので、簡単に実装していきます。

ldcgetstatic などのニーモニックは一方でオペコードと対になっていて、それぞれ番号で表すことができます。

JVM Spec より下記の通りになります。

ニーモニック
オペコード
オペランド

getstaitc
0xB2
2 bytes

ldc
0x12
1 byte

invokevirtual
0xB6
2 bytes

return
0xB1
none

CodeAttribute にはオペコードで格納されており、実行されるコードは下記の通りになります。

B2 00 02 12 03 B6 00 04 B1

この値を [, ] で囲ったものがオペコード, <, > で囲ったものがオペランドとすると下記のようになります。

[B2] <00 02> [12] <03> [B6] <00 04> [B1]

このように、 [, ] で囲った部分で処理を分離していき、 <, > で囲った部分を使ってオペランドスタックに積んだり、何かしら計算をしたりしていくことになります。

実際に処理をする JavaScript を書くと下記のようになります。

while (true) {

const opcode = codeStream.read(1)[0];
let operand = null;

switch (opcode) {
case 0xB2: // getstatic
operand = codeStream.readUnsignedShort();
operandStack.push(cp[operand]);
break;
case 0x12: // ldc
operand = codeStream.read(1)[0];
operandStack.push(cp[cp[operand].stringIndex]);
break;
case 0xB6: // invokevirtual
const cpInfo = cp[codeStream.readUnsignedShort()];
const nameAndType = cp[cpInfo.nameAndTypeIndex];

const methodName = cp[nameAndType.nameIndex].text;
const descriptor = cp[nameAndType.descriptorIndex].text;

const methodArguments = [];
for (let i = 0; i < descriptor.split(';').length - 1; i++) {
methodArguments.push(operandStack.pop());
}

const context = operandStack.pop();
const baseClass = cp[cp[context.classIndex].nameIndex].text;
const baseClassTarget = cp[cp[context.nameAndTypeIndex].nameIndex].text;

const classPath = baseClass.replace(/\//g, '.');
const initiatedClass = new classes[classPath];

initiatedClass[baseClassTarget][methodName](...methodArguments);
break;
case 0xB1: // return
return;
default:
throw new Error(`Unknown opcode: ${opcode}`);
}
}

それぞれのオペコードの命令について上記でも軽く触れていますが、 JVM Spec に詳しく書いてあるので詳しく知りたい方は下記を見るといいかもです。

また、 classes には雑に Java のクラスを定義します。


const classes = {
'java.lang.System': class {
constructor() {
this.out = new classes['java.io.PrintStream']()
}
},
'java.io.PrintStream': class {
println(...args) {
document.querySelector('#output').append(
(new TextDecoder()).decode(Uint8Array.from(args[0].bytes))
);
}
}
};


上手く行くと Hello World が出力されます

JS-JVM-Sample.gif


2019/09/10 追記

二日前に下記投稿しました