# 2024/05/10 工作日志

### 好久不见！

在二月份的时候，本项目就已经开发完成，为了让项目准备更充分，我决定进行更新。

本次的更新将会从语法分析器直接跳跃到完整的编译器、虚拟机。

### 更新了依赖库

本次新增了``BinaryReader.hpp``、``BinaryWriter.hpp``和``ByteMap.hpp``。

这三个库的接口定义都较为简单，故不详解，只需花费两分钟即可了解新增的库。

``ByteMap``的接口定义和其他Map类的差别不大。我认为唯一要解释的就是``BinaryWriter``中的``write_i``是 **Write Integer（写入整形）** 的缩写。

虽然新增的内容不多，但是在标准C实现的依赖库中（即``stdc_implemented``目录下的源码），我进行了大量的翻新，其翻新的目的主要是为了优化。

下面我将挑选变动最大的``ArrayList.hpp``和``String.hpp``进行讲解。

<br>

1. 首先是``ArrayList``

<br>

原先的ArrayList采用**用多少给多少**的内存分配机制：新增一个元素，就realloc一次，删除一个元素，还是realloc一次。

显然这种机制在理论上不浪费一丁点内存，但在实际上容易造成大量的内存碎片，并且性能损耗太多。

在此基础下，我根据[min0911_](https://github.com/min0911Y)的建议（感谢），采取了**双倍扩容法**。

双倍扩容法的机制能概括为：

* 内存占用只增不减
* 如果内存不够用，就按照原内存占用大小进行双倍扩容

这可以使整个程序关于ArrayList内存分配的时间复杂度从线性级降为对数级。

<br>

1. 其次是``String``

<br>

String也曾和ArrayList一样，所以我进行了优化。

String的优化则采用栈缓存法。

栈缓存法的机制能概括为：

* 设立一个位于栈的内存块S（默认S的大小为32字节，该大小可自定义）
* 如果S能够存的下数据（即数据占用的大小**小于**S的大小），就用S存储，否则使用内存分配

在程序运行当中，经常出现一些长度较小的String，完全可以使用栈进行缓存，这样甚至用不到内存分配。

3. 最后我们来看看优化成果

**本次统计了虚拟机运行程序时在后台的内存分配次数，当时采用了计数器来计数内存分配次数，不过由于年代久远，具体数据可能会记错，所以会有微小差别，实验并不严谨，仅供参考。**

||String|ArrayList|
|--|--|--|
|优化前|270300次|5785次|
|优化后|0次|837次|

值得注意的是，String的内存分配次数在优化后达到了0次！这也就意味着程序在运行过程中，单个String的内存占用都没有超过32字节。

### 去除了预处理器

我去除了预处理器，并更改了架构。

### 更新了Ast

``src/ast``目录下的变动较大，删除了SFNName节点，并新增了DefVar节点，最后补充了所有Ast类的构造函数。这些节点主要是为了运行时而变动的。

但是Ast的理论架构有变：编译时生成的Ast和运行时的Ast在叶子节点上有略微差别，后续的**写了Ast与AstIr之间的互转工具**部分会提及，为了区分，我们将运行时的Ast称为**Running-Ast**。

### 更新了DataType

``src/data_type``目录下的变动不多，主要变动位于MethodType。下面讲解一下与MethodType有关的原理。

在Stamon中。所有的函数对象都拥有自己的**容器**，对全局函数而言，它的容器为``null``；对类成员函数而言，它的容器就是它所在的类对象。

例如有一下stamon源码：

```
func f {}

class cls {
    func f(self) {}
}

def obj = cls.new;
```

其中f的容器就为``null``，而obj.f的容器则是obj本身。

利用容器的机制，在调用类成员函数时，可以将其容器传给self，从而实现类成员函数访问其他成员。

而在MethodType当中，容器的实现则是：
```C++
ObjectType* container; //容器
```

<br>

### 完成了编译器

这些源码位于``src/compiler``目录下

我们规定：Stamon源码的文件后缀为``.st``

词法分析器的变动不大。所以我们先来看看语法分析器。

目前的语法分析器已经没有已知bug了。本次的更改也着重于实现对多文件的语法分析。

最重要的是新增的``Compiler.hpp``，Compiler主要对编译器进行了封装。你只需要向Compiler提供相应的参数，就能实现编译。

以下是Compiler的讲解：

* ``Compiler(STMException* e)``：构造函数，需要传入异常类。
* ``void compile(String filename, bool isSupportImport)``：编译源码，``filename``为需要编译的源码文件名，``isSupportImport``声明了是否支持导入其他源码（有些平台并不支持多文件操作，所以我设置了这个参数），如果源码当中需要导入源码，则报错。在执行该函数之后应该要检查是否存在异常。编译出的结果会存入``src``成员。
* 这里需要补充的是：``src``成员的类型为``ArrayList<SourceSyntax>``，其中，``SourceSyntax``定义于``Parser.cpp``。``SourceSyntax``由``ast::AstNode* program（单个文件的语法树）``和``String filename（文件名）``构成。

### 编写了Ast与AstIr之间的互转工具

这些工具位于``src/ir``目录下

``AstIr``是一种中间代码表示形式，可以将Ast展开为一个数组。这样就可以把Ast转为AstIr，并将AstIr以字节码的方式写入。读取时也只需要读取AstIr，并重组成Ast即可。

AstIr的格式和HTML的格式类似：由逻辑单元、数据单元和结束单元组成。一棵Ast可以通过深度优先遍历转为AstIr。

这样的描述也许会较为拗口，我们来看一个示例：

> 考虑以下Ast:
> ```
> Add
> |-a
> |-Sub
> |--b
> |--1
> ```
> 该Ast可以转为以下AstIr：
> ```
> <Add>         //此为逻辑单元，以此类推
> <data val=a>  //此为数据单元，以此类推
> <Sub>
> <data val=b>
> <data val=1>
> <end>         //此为结束单元，以此类推
> <end>
> ```
> 这段AstIr和上面的Ast本质上是等价的。这样只需将Ast转为AstIr，就能获得一系列单元，方便存入文件。

逻辑单元本质上就是Ast节点的非叶子节点，数据单元本质上就是Ast节点的叶子节点。

我们先来讲一讲``AstIr.cpp``。

AstIr单元的实现是：

```C++
class AstIr {
    public:
        int type;
        /*
            * 一些特别的规定
            * 当type为-1，代表这是一个结束符，即</>
            */
        int data;
        //如果这个IR是字面量或标识符，则data存储着其在常量表中的下标
        //否则存储这个IR的具体信息（例如运算符类型）
        String filename;	//IR所在的文件名
        int lineNo;	//IR所在的行号
};
```

由于Ast当中的叶子节点只有两种可能：标识符或字面量，所以我把两者统一了起来，设立了``DataType``的子类``IdenConstType``，这样常量表里也能存储标识符了。

而数据单元作为Ast的叶子节点，他的type统一为AstLeafType。其中AstLeaf是专门为了运行时而定制的。

> ``Ast``和``Running-Ast``的区别就在于：Running-Ast的叶子节点皆为``AstLeaf``，而Ast非然。

AstIrGenerator类用于将Ast数据生成为AstIr（同时兼任着AstIr转Running-Ast的任务），它值得关注的接口有：

* ``ArrayList<AstIr> gen(AstNode* program)``：迭代遍历语法树，编译成AstIr
* ``AstNode* read(ArrayList<AstIr> ir)``：AstIr转Ast，如果ir不正确，程序会运行时错误，所以请在运行该函数前检查ir

至此，Stamon的源码将会被转为AstIr，接下来则是写入AstIr至文件了，这一部分的内容位于``src/Stamon.hpp``，暂时按下不表，在介绍完解释器后会解释。


### 完成了SFN机制

SFN机制在本项目原所在仓库中有提及，这里再次摘抄：

> SFN，全称Stamon For Native。是StamonVM的一个调用外部功能的机制。你可以用它与解释器交互。

用不太准确但方便理解的说法是：SFN和JNI类似，都是一种本地库调用机制。

SFN的源码位于``src/sfn/SFN.cpp``。

SFN在Stamon中的语法规定为``sfn port, arg;``，其中port必须为整数（默认范围为0~65536），代表着端口号，使用不同的端口号会调用不同的本地库（类似于汇编中的IO），arg则是参数，在调用SFN后，arg可能会变为调用后的结果。

SFN中的本地库可以由用户自定义，可扩展性高，不过我认为应该要给SFN划分具体的标准，哪一部分端口保留用作标准的本地库，哪一部分交给用户自定义。我可能会在后续进行调整。

SFN类的主要接口有：

* ``SFN(STMException* e, vm::ObjectManager* objman)``：构造函数，e为异常类，objman为当前运行时的ObjectManager对象。你可以在构造函数里绑定自己的本地库。详细请参见源码。
* ``void call(int port, datatype::Variable* arg)``：根据端口号调用本地库。

### 完成了虚拟机

虚拟机的运行原理为：将二进制文件读取为AstIr，交给AstIrGenerator类解析为Running-Ast，最后交给``vm/AstRunner.cpp``递归运行。

我们规定：Stamon编译后的二进制文件为**STVC文件**，文件后缀为``.stvc``

我们来逐步讲解。

首先是二进制文件读取为AstIr，这部分的实现位于``src/vm/STVCReader.cpp``，STVCReader类的主要接口有：

* ``STVCReader(char* vmcode, int code_size, STMException* e)``：构造函数，vmcode为字节码在内存中的地址，code_size指字节码的大小，e为异常类
* ``bool ReadHeader()``：读取字节码头，读取失败则抛出异常并返回false，否则返回true
* ``ArrayList<AstIr> ReadIR()``：读取AstIr，返回由AstIr组成的ArrayList

想要完整的读取一个STVC文件，应该要先创建一个STVCReader对象，然后先调用``ReadHeader``读取文件头信息，接着调用``ReadIR``来读取AstIr。调用这两个函数之后要分别检查是否有异常抛出。

接着是让AstIrGenerator类解析为Running-Ast，这一部分在**写了Ast与AstIr之间的互转工具**部分里已经详细提及过了，故不再赘述。

最后是交给``vm/AstRunner.cpp``递归运行，``AstRunner``类采用了和语法分析器类似的结构，下面我们来看看重点的数据接口及接口：

AstRunner在递归执行Ast时的返回值为``RetStatus``类。RetStatus，全称*Return-Status（返回状态）*，用于指示当前代码运行状况，我们来看看RetStatus的定义：

```C++
class RetStatus {	//返回的状态（Return Status）
        //这个类用于运行时
    public:
        int status;	//状态码
        Variable* retval;	//返回值（Return-Value），无返回值时为NULL
        RetStatus() {}
        RetStatus(const RetStatus& right) {
            status = right.status;
            retval = right.retval;
        }
        RetStatus(int status_code, Variable* retvalue) {
            status = status_code;
            retval = retvalue;
        }
    };
```

其中的``int status``一行用于存储状态码，状态码有以下几类：

```C++
enum RET_STATUS_CODE {	//返回的状态码集合
    RetStatusErr = -1,	//错误退出（Error）
    RetStatusNor,		//正常退出（Normal）
    RetStatusCon,		//继续循环（Continue）
    RetStatusBrk,		//退出循环（Break）
    RetStatusRet		//函数返回（Return）
};
```

AstRunner的主要接口有：

1. 抛出运行时异常，这些异常分别是：

```C++
void ThrowTypeError(int type);
void ThrowPostfixError();
void ThrowIndexError();
void ThrowConstantsError();
void ThrowDivZeroError();
void ThrowBreakError();
void ThrowContinueError();
void ThrowArgumentsError(int form_args, int actual_args);
void ThrowReturnError();
void ThrowUnknownOperatorError();
void ThrowUnknownMemberError(int id);
```

2. 利用excute方法执行Running-Ast，它的函数原型是：

```C++
RetStatus excute(
    AstNode* main_node, bool isGC, int vm_mem_limit,
    ArrayList<DataType*> tableConst, ArrayList<String> args,
    STMException* e
);
```

虚拟机在执行过程中会向ObjectManager申请对象，来实现GC机制。

### 编写了命令行工具

命令行工具的内容主要位于``src/Main.cpp``和``src/Stamon.hpp``

我们先来看一看Stamon类。

以下是他的主要接口：

* ``Stamon()``：构造函数
* ``void Init()``：初始化
* ``void compile(String src, String dst,bool isSupportImport)``：编译程序，src为源码名，dst为目标二进制文件名，isSupportImport表示是否支持导入源码
* ``void run(String src, bool isGC, int MemLimit)``：运行程序，src为运行的二进制文件名，isGC表示是否支持GC机制，MemLimit表示如果支持GC机制的话，对象占用内存的最大限制。

``Main.cpp``的内容主要是命令行解析之类，不再赘述。但是值得注意的是：Main.cpp并不是完全可移植，由于涉及到了平台函数，所以目前仅支持``Linux``、``Windows``、``MacOS``。开发者可以参考该文件自定义命令行工具。

### 合并原先的文档

我把项目所在的原仓库的工作日志也加入了进来。

### 运行环境

本项目于Windows环境上调试并具有可移植性，所以如果作为用户，请尽量选择在Windows平台上运行以确保最佳体验。

在运行时，请确保您以配置环境变量，具体的配置方法为：设置一个新的名为**STAMON**的环境变量，其变量值为可执行文件所在目录的路径，**路径末尾不要有类似"\"或"/"的分隔符！**

### 可执行文件架构

可执行文件位于``bin/``目录下，``bin/include``目录下为标准库。

在命令行中键入"stamon --help"即可获取stamon的具体使用方法。

### 编译方法

改自``20230916.md``：

我在根目录下编写了Makefile。

其中，Makefile的主要用法是：
* make release：编译发行版

目前，Makefile能在Windows系统下使用，如果想要在其他系统编译，可以更改Makefile。

编译项目之前，需要确保拥有以下工具（附我的工具版本，可以参考）：

1. make：GNU Make 3.82.90
2. gcc：gcc (x86_64-posix-seh-rev1, Built by MinGW-Builds project) 13.1.0
3. strip：GNU strip (GNU Binutils) 2.39
4. upx：upx 4.0.2

### 接下来要做的事

1. 编写AST的解释器
2. 编写词法分析的保存功能
3. 编写AST的O1优化器
4. 完善标准库