pipeline-script

脚本引擎运行流程： 分词（产生Token）->解析生成AST->宏函数展开->编译为LLVM IR ->调用LLVM JIT执行器执行

Lexer（分词器）->产生Token,into_iter()返回一个TokenStream Parser(解析器)->生成AST(Module,Function,Struct,Module,CLass,Stmt,Expr)，parse_file()返回一个Module Compiler(编译器)->生成LLVM IR,compile_module返回一个LLVMModule

Engine（引擎）->run_function调用LLVM JIT执行器执行LLVMModule,run_file()依次调用分词器，解析器，编译器，按照流程执行

难点

宏函数展开 动态参数实现，Any类型，Trait类型

主要逻辑梳理

1. 变量

变量分为值，引用和指针，const声明的都是值，let会声明一个变量，指针常常作为参数和返回值，目的是兼容ffi的第三方接口

• compile_member和compile_index 分为值和引用，目标是值使用extract_value，返回的是字段的值，引用返回的是字段的指针，member为左值的时候，因为需要得到指针，需要保证目标是引用，如果目标是指针，和引用一同处理，所以只需要考虑Type::ref和Type::pointer这两者使用getelementpointer,其余都是提取值就行，对泛型进行特殊考虑，一般是泛型实例，需要转成非泛型类型，几乎所有泛型的地方都需要获得它的实例类型，可以抽象一个新方法get_instance_type，对于其他类型，返回他们自身，对于泛型实例，返回它的实例，因为ref和pointer处理逻辑是一样的，可以考虑一个通用方法进行判断，get_underlying_type将ref转成pointer,将泛型实例转成实例在进行递归转换，有ref变成pointer.

考虑特殊情况self.data[index] = 1,self是引用，data是指针，

对于引用对象，有左值应用和右值引用之分，左值取指针，右值取引用值

以上例子中，self.data[index]是左值，尽量取指针，self（获取变量指针），self.data获取data元素的指针，因为data原本就是一个指针，此处获取的是指针的指针，因为self[index]本质上是对self指针进行偏移index计算，self是指针的时候，该语法成立，但是self实际上是指向一个变量的指针，因此，index只能允许原本值是指针才能进行，在左值语境中，index操作前需要进行一次额外的load。那我们接着考虑index在右值的情况，吧b = self.data[index],self是结构体，self.data取结构体变量获取指针data,进行index操作，获取便宜后的指针，最后进行load.

总结：对于index操作，左值，先load再index;右值，先index再load.

对于member操作，左值使用getelementptr,右值使用提取，target在左值会保证是指针，在右值会保证是结构体值

关于类型系统，原则上，compile_xxx函数的返回值是Value，不包含Type，但是有些时候我们系统进行一些类型约束，比如函数调用，函数的参数可能是分为值类型和引用类型，FunctionCall结构体包含了调用的函数，我们编译的时候可以获取到函数的类型，检查函数参数，检查函数的形参和实参类型是否匹配，此时实参还是expr，当形参是Type::Ref时，调用左值求职，当不是ref的时候调用右值求职，这里需要考虑一下指针的特殊参数类型，是否可以应用右值求职，以下是一个例子：

const p = malloc()
memread(p)

p是一个指针，使用const声明，注册的符号是(p,pointer),如果使用let声明，注册的符号是p,ref(p)指向指针的指针，可以改变指针指向的内容空气，const无法改变指向的内存空间。

当执行到FunctionCall时，p是指针类型，直接执行右值，获取p符号的类型，发现不是ref，不会进行额外求值load，返回指针，OK。

所以对于函数参数来说，也只需要考虑值（左值）类型和引用（右值）类型。

从以上例子也可以看出符号表应该存储Type，因为要知道是否是引用类型，引用类型在右值环境会额外求值，但是能否移除符号表的类型呢，似乎可以，那就是给Value引入RefValue,这似乎局不需要再符号表存储额外的类型信息，符号表就是简单的（String,Value）映射，那函数类型的形参类型声明是否有必要呢，考虑以上例子中的函数，memread,符号是memread，符号表是FunctionValue声明，我们需要获取其函数形参声明，需要根据参数名（默认值系统）和根据下标获取形参类型，以下是对FunctionValue结构体的构思：

struct FunctionValue{
    reference:LLVMValueRef
    index_map:Hashmap<String,usize>
    param_types:Vec<Type> // 这里的type似乎无法避免，不然如何获取形参类型呢,这里还需要记录形参默认值，能够直接通过Value声明类型呢，用一种新的类型的空值来表示没有默认值，并且这种空值无法被用户声明，避免默认值就是空值的情况，非空值就是有默认值，这里似乎可以参考js的undefined,因此引入UndefValue,但是如何兼容诸多的值类型，比如Int64Value,FloatValue呢，他们也有空值吧，哦，对了，为每个Value定义一个undef方法，llvm-sys似乎可以定义类型空值，因此我们可以约束下Valeu的trait
}

trait IValue {
    // get_type(&self)->Type 该方法似乎没有必要
    fn get_llvm_type(&self,ctx:&Context)->LLVMType
    fn as_ref(&self)->LLVMValueRef
    fn get_undef(&self)-> Self
    // 现在问题是该函数怎么实现，undef声明后的返回值也是LLVMValueRef,如何判断它是不是空类型呢，取看看LLVM-sys是否有支持判断LLVMValueRef是否是空类型。
    // 查阅后发现确实存在对应的函数，LLVMGetUndef和LLVMIsUndef,所以函数值也可以不包括Type了，这样在编译过程中Type已经被消除了。
    fn is_undef(&self)->bool
}

其次我们还注意到 一个问题，那就是LLVMType，类型在一个上下文中实际上是单例，通过LLVMXxxType()声明一次后可以无限次使用，而考虑到LLVMType返回的也是一个LLVMTypeRef,因此可能即时无限次调用LLVMType创建类型，都是返回的同一个类型引用。结果确实是对的，因此我对于基本类型直接调用LLVMXxxType返回即可。

对于复杂类型，比如结构体，如何获得他们的LLVMType呢，一个结构体有名字，有字段。这个时候一般是创建命名结构体和非命名结构体两种，如果StructValue有名字则，采用命名结构体，没有，则无命名结构体，考虑到命名结构体创建确实比较复杂，而且创建命名结构体值时需要检查结构体的类型约束，因此需要存储他们的类型，在第一次编译模块时编译所有结构体，存在ctx中， 以后的结构体值有名字时，直接获取结构体类型，进行检查，因此get_llvm_type()应该有一个入参ctx,对于Type的get_llvm_type也应该有一个ctx入参，类型都通通ctx创建，比如ctx.llvm_float_type()

另外，对于更复杂一点的类型和值系统，枚举，llvm本身并没有原生支持枚举，需要我们通过struct进行枚举，我们初步设定枚举的值是tag+字节数组，并通过bitcast进行转换。因此，它的value定义可以是以下的样子：

struct EnumValue{
    name:(String,String) // 枚举名和变体名
    tag:Int64Value
    data:ArrayValue
}
//其llvm_type应该是一种结构固定的结构体，
LLVMType::Enum(EnumLLVMType)

struct EnumLLVMType{
    reference:LLVMTypeRef
    // 标签和变体映射
    variant_tag:Hashmap<string,Int64Value>
}

对value系统进行重设计，目前的value包括type和llvmValue,但是实际上llvmValue就包扩了类型信息，type实际上可以只存在于AST阶段，然后现在构建都是通过builder实现的，但是对于一个IntValue应该可以是啊a.add()另外一个IntValue

enum Value{
    Bool(BoolValue)
    Int8(Int8Value)
    Int16(Int16Value)
    Int32(Int32Value)
    Int64(Int64Value)
    Float(FloatValue)
    Double(DoubleValue)
    String(StringValue)
    Struct(StructValue)
    Pointer(PointerValue)
    Function(FunctionPointer)
    Array(ArrayValue)
}

struct PointerValue{
    element: Box<Value>
    value:Option<Value>
}

impl PointerValue{
    fn get_value()->Value {
        match self.value
    }
    fn get_element_pointer()
}
struct Int64Value {
    value:LLVMValueRef
}

impl Int64Value {
    fn add(&self,ctx:&Context,value:Int64Value)->Int64Value
    fn add_i8(&self,ctx:&Context,value:Int8Value)
}

四、编译前端设计与实现

4.1 词法分析器设计

词法分析器作为编译器的第一道处理环节，其设计直接影响到整个编译过程的效率和可靠性。本系统采用基于Logos库的词法分析器实现，主要考虑以下几个方面：

4.1.1 Token定义

系统定义了完整的Token集合，采用Rust枚举类型实现：

#[derive(Logos, Debug, PartialEq, Clone)]
pub enum Token {
    // 字面量类型
    #[regex(r#""([^"\\]|\\.)*""#, |lex| lex.slice().to_string())]
    String(String),
    
    #[regex(r#"f"([^"\\]|\\.)*""#, |lex| lex.slice().to_string())]
    FormatString(String),
    
    #[regex(r"[0-9]+", |lex| lex.slice().parse())]
    Int(i64),
    
    #[regex(r"[0-9]+\.[0-9]+", |lex| lex.slice().parse())]
    Float(f32),
    
    // 标识符和关键字
    #[regex(r"[a-zA-Z_][a-zA-Z0-9_]*", |lex| {
        let slice = lex.slice();
        match slice {
            "true" => Token::Boolean(true),
            "false" => Token::Boolean(false),
            _ if KEYWORDS.contains(&slice) => Token::Keyword(slice.to_string()),
            _ => Token::Identifier(slice.to_string()),
        }
    })]
    Identifier(String),
    
    // 运算符和分隔符
    #[token("(")] BraceLeft,
    #[token(")")] BraceRight,
    #[token("[")] BracketLeft,
    #[token("]")] BracketRight,
    #[token("{")] ParenLeft,
    #[token("}")] ParenRight,
    #[token(".")] Dot,
    #[token(":")] Colon,
    #[token("::")] ScopeSymbol,
    #[token("=")] Assign,
    #[token(",")] Comma,
    #[token("+")] Plus,
    #[token("-")] Minus,
    #[token("*")] Star,
    #[token("/")] Slash,
    #[token("%")] Mod,
    #[token(">")] Greater,
    #[token("<")] Less,
    #[token("==")] Equal,
    #[token("!=")] NotEqual,
    #[token("->")] Arrow,
    #[token("!")] Negate,
    #[token("&&")] And,
    #[token("|")] Vertical,
    #[token("@")] Annotation,
    #[token("&")] BitAnd,
    
    // 错误和空白处理
    #[error]
    #[regex(r"[ \t\n\f]+", logos::skip)]
    Error,
}

4.1.2 实现策略

4.1.2.1 基于查找表的快速分词算法

本系统采用Logos库提供的自动生成词法分析器功能，其核心是基于查找表的快速分词算法。该算法通过以下方式实现高效分词：

1. 关键字查找优化

lazy_static! {
    static ref KEYWORDS: HashSet<&'static str> = {
        let mut set = HashSet::new();
        set.insert("fn");
        set.insert("let");
        set.insert("const");
        set.insert("if");
        set.insert("else");
        set.insert("while");
        set.insert("for");
        set.insert("return");
        set.insert("break");
        set.insert("continue");
        set
    };
}

2. 状态机优化

pub struct Lexer<'a> {
    source: &'a str,
    position: usize,
    line: usize,
    column: usize,
    tokens: Vec<Token>,
    errors: Vec<LexError>,
}

impl<'a> Lexer<'a> {
    pub fn new(source: &'a str) -> Self {
        Lexer {
            source,
            position: 0,
            line: 1,
            column: 1,
            tokens: Vec::new(),
            errors: Vec::new(),
        }
    }
    
    pub fn tokenize(&mut self) -> Result<Vec<Token>, Vec<LexError>> {
        let mut lexer = Token::lexer(self.source);
        while let Some(token) = lexer.next() {
            match token {
                Ok(tok) => self.tokens.push(tok),
                Err(_) => self.errors.push(LexError::new(
                    self.line,
                    self.column,
                    "Invalid token"
                )),
            }
            self.update_position(&lexer);
        }
        if self.errors.is_empty() {
            Ok(self.tokens.clone())
        } else {
            Err(self.errors.clone())
        }
    }
}

4.1.2.2 批量读取机制

系统实现了高效的批量读取机制，通过缓冲区技术优化I/O性能：

pub struct SourceReader {
    buffer: Vec<u8>,
    buffer_size: usize,
    position: usize,
    file: File,
}

impl SourceReader {
    pub fn new(path: &Path, buffer_size: usize) -> io::Result<Self> {
        let file = File::open(path)?;
        Ok(SourceReader {
            buffer: Vec::with_capacity(buffer_size),
            buffer_size,
            position: 0,
            file,
        })
    }
    
    pub fn read_chunk(&mut self) -> io::Result<&[u8]> {
        self.buffer.clear();
        self.file.read_to_end(&mut self.buffer)?;
        Ok(&self.buffer)
    }
}

4.1.2.3 错误恢复机制

系统实现了完善的错误恢复机制，确保在遇到错误时能够继续解析：

#[derive(Debug, Clone)]
pub struct LexError {
    line: usize,
    column: usize,
    message: String,
}

impl LexError {
    pub fn new(line: usize, column: usize, message: &str) -> Self {
        LexError {
            line,
            column,
            message: message.to_string(),
        }
    }
    
    pub fn to_string(&self) -> String {
        format!("Error at line {}, column {}: {}", 
            self.line, self.column, self.message)
    }
}

pub struct ErrorRecovery {
    errors: Vec<LexError>,
    recovery_points: Vec<usize>,
}

impl ErrorRecovery {
    pub fn new() -> Self {
        ErrorRecovery {
            errors: Vec::new(),
            recovery_points: Vec::new(),
        }
    }
    
    pub fn add_error(&mut self, error: LexError) {
        self.errors.push(error);
    }
    
    pub fn add_recovery_point(&mut self, position: usize) {
        self.recovery_points.push(position);
    }
}

4.1.2.4 Unicode支持

系统通过UTF-8编码处理实现了完整的Unicode支持：

pub struct UnicodeProcessor {
    decoder: Decoder,
}

impl UnicodeProcessor {
    pub fn new() -> Self {
        UnicodeProcessor {
            decoder: Decoder::new(),
        }
    }
    
    pub fn process_char(&mut self, c: char) -> Result<(), UnicodeError> {
        if c.is_alphabetic() || c == '_' {
            Ok(())
        } else {
            Err(UnicodeError::InvalidIdentifier)
        }
    }
}

4.1.2.5 位置信息追踪

系统实现了精确的位置信息追踪，用于错误报告和调试：

#[derive(Debug, Clone, Copy)]
pub struct Position {
    pub line: usize,
    pub column: usize,
    pub offset: usize,
}

impl Position {
    pub fn new() -> Self {
        Position {
            line: 1,
            column: 1,
            offset: 0,
        }
    }
    
    pub fn advance(&mut self, c: char) {
        self.offset += 1;
        if c == '\n' {
            self.line += 1;
            self.column = 1;
        } else {
            self.column += 1;
        }
    }
}

4.1.2.6 性能优化

系统通过多种技术实现性能优化：

1. SIMD加速

#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;

pub unsafe fn simd_process_chunk(chunk: &[u8]) -> Vec<u8> {
    let mut result = Vec::with_capacity(chunk.len());
    let mut i = 0;
    while i + 16 <= chunk.len() {
        let data = _mm_loadu_si128(chunk.as_ptr().add(i) as *const __m128i);
        // SIMD处理逻辑
        i += 16;
    }
    result
}

2. Token缓存

pub struct TokenCache {
    cache: LruCache<String, Vec<Token>>,
    max_size: usize,
}

impl TokenCache {
    pub fn new(max_size: usize) -> Self {
        TokenCache {
            cache: LruCache::new(max_size),
            max_size,
        }
    }
    
    pub fn get(&mut self, key: &str) -> Option<&Vec<Token>> {
        self.cache.get(key)
    }
    
    pub fn put(&mut self, key: String, tokens: Vec<Token>) {
        self.cache.put(key, tokens);
    }
}

4.1.2.7 LLVM集成

系统通过LLVM JIT编译器实现高效的代码生成和执行。词法分析器与LLVM的集成主要体现在以下几个方面：

1. LLVM上下文管理 LLVM上下文是LLVM系统的核心组件，负责管理编译过程中的所有资源。在本系统中，我们创建了一个LLVMContext结构体来封装LLVM的上下文管理。该结构体包含以下关键组件：

• context: LLVM的上下文对象，用于管理类型系统和符号表
• module: LLVM模块，用于组织编译单元
• builder: IR构建器，用于生成LLVM IR指令
• execution_engine: JIT执行引擎，用于动态编译和执行代码

上下文管理的主要职责包括：

• 初始化LLVM环境
• 创建和管理编译模块
• 设置IR构建器
• 配置JIT执行引擎
• 资源清理和释放

2. Token到LLVM IR的转换 Token到LLVM IR的转换是词法分析器与LLVM集成的关键环节。我们实现了TokenToIRConverter结构体来处理这一转换过程。该转换器的主要功能包括：

• 类型映射：将Token类型映射到对应的LLVM类型

  • 整数类型映射到LLVM的整数类型
  • 浮点数映射到LLVM的浮点类型
  • 字符串映射到LLVM的数组类型

• 值转换：将Token的值转换为LLVM常量

  • 整数转换为LLVM整数常量
  • 浮点数转换为LLVM浮点常量
  • 字符串转换为LLVM全局常量

• 符号表管理：维护变量和函数的符号表

  • 记录变量名到LLVM值的映射
  • 处理作用域和生命周期
  • 支持符号重定义检测

3. 优化通道配置 LLVM提供了丰富的优化通道，我们通过OptimizationPasses结构体来管理和配置这些优化通道。优化通道分为两个层次：

• 函数级优化：

  • 指令组合优化：合并相邻的指令
  • 重关联优化：重新组织表达式以优化计算
  • 全局值编号：消除冗余计算
  • CFG简化：优化控制流图

• 模块级优化：

  • 常量合并：合并相同的常量
  • 死代码消除：移除未使用的代码
  • 全局优化：优化全局变量和函数
  • 函数内联：内联小函数调用

4. JIT编译执行 JIT（即时编译）执行是系统的核心功能，通过JITExecutor结构体实现。执行流程包括：

• 初始化阶段：

  • 创建LLVM上下文
  • 设置优化通道
  • 准备执行环境

• 编译阶段：

  • 将Token转换为LLVM IR
  • 创建主函数和基本块
  • 生成IR指令
  • 运行优化通道

• 执行阶段：

  • 验证模块的正确性
  • 获取函数指针
  • 执行编译后的代码
  • 处理执行结果

5. 内存管理 内存管理是确保系统稳定运行的关键。我们实现了以下内存管理机制：

• 资源生命周期管理：

  • 使用Rust的所有权系统管理LLVM资源
  • 实现Drop trait确保资源正确释放
  • 处理资源泄漏和重复释放

• 安全的内存访问：

  • 使用unsafe块封装LLVM的C API调用
  • 实现边界检查和空指针检测
  • 处理内存分配失败的情况

• 错误处理：

  • 实现错误恢复机制
  • 提供详细的错误信息
  • 支持优雅的资源清理

6. 性能优化 为了提高系统的性能，我们实现了以下优化策略：

• 编译时优化：

  • 使用LLVM的优化通道
  • 实现常量折叠
  • 优化控制流

• 运行时优化：

  • 实现JIT缓存
  • 优化内存分配
  • 减少不必要的复制

• 并行处理：

  • 支持多线程编译
  • 实现任务并行
  • 优化资源竞争

7. 错误处理 系统实现了完善的错误处理机制：

• 编译错误：

  • 语法错误检测
  • 类型错误检查
  • 语义错误验证

• 运行时错误：

  • 内存访问错误处理
  • 类型转换错误处理
  • 资源分配错误处理

• 错误恢复：

  • 实现错误恢复点
  • 支持错误上下文保留
  • 提供错误诊断信息

4.2 语法分析器设计

语法分析器负责将Token流转换为抽象语法树(AST)，本系统采用递归下降法实现。

4.2.1 AST结构设计 系统定义了完整的AST节点类型：

enum Expr {
    Literal(Literal),        // 字面量表达式
    Binary(BinaryExpr),      // 二元运算表达式
    Unary(UnaryExpr),        // 一元运算表达式
    Call(CallExpr),          // 函数调用表达式
    Member(MemberExpr),      // 成员访问表达式
    Index(IndexExpr),        // 数组索引表达式
    Identifier(Identifier),  // 标识符表达式
    Block(BlockExpr),        // 代码块表达式
    If(IfExpr),             // 条件表达式
    Loop(LoopExpr),         // 循环表达式
    Break,                  // 中断语句
    Continue,               // 继续语句
    Return(Option<Box<Expr>>), // 返回语句
}

enum Stmt {
    Let(LetStmt),           // 变量声明语句
    Const(ConstStmt),       // 常量声明语句
    Expr(Expr),             // 表达式语句
    Return(Option<Expr>),   // 返回语句
    Break,                  // 中断语句
    Continue,               // 继续语句
}

struct Module {
    items: Vec<Item>,       // 模块项列表
}

enum Item {
    Function(Function),     // 函数定义
    Struct(Struct),         // 结构体定义
    Enum(Enum),             // 枚举定义
    TypeAlias(TypeAlias),   // 类型别名
    Import(Import),         // 导入语句
}

4.2.2 语法分析策略

1. 递归下降解析
2. 错误恢复和报告机制
3. 语法糖转换
4. 宏展开处理

4.3 语义分析器设计

语义分析器负责类型推导、类型检查和符号表管理，是确保程序语义正确性的关键环节。

4.3.1 类型系统设计 系统定义了完整的类型系统：

enum Type {
    Bool,                   // 布尔类型
    Int8, Int16, Int32, Int64, // 整数类型
    Float, Double,          // 浮点类型
    String,                 // 字符串类型
    Array(Box<Type>, usize), // 数组类型
    Struct(StructType),     // 结构体类型
    Enum(EnumType),         // 枚举类型
    Function(FunctionType), // 函数类型
    Pointer(Box<Type>),     // 指针类型
    Reference(Box<Type>),   // 引用类型
    Generic(String),        // 泛型类型
    Any,                    // 任意类型
}

struct FunctionType {
    params: Vec<Type>,      // 参数类型列表
    return_type: Box<Type>, // 返回类型
    is_variadic: bool,      // 是否可变参数
}

struct StructType {
    name: String,           // 结构体名称
    fields: Vec<(String, Type)>, // 字段列表
}

struct EnumType {
    name: String,           // 枚举名称
    variants: Vec<(String, Option<Type>)>, // 变体列表
}

4.3.2 语义分析策略

1. 类型推导系统
2. 泛型类型和函数处理
3. 类型检查机制
4. 作用域和符号表管理
5. 闭包捕获分析

4.4 LLVM IR生成器设计

LLVM IR生成器负责将AST转换为LLVM中间表示，是连接前端和后端的关键组件。

4.4.1 代码生成流程

1. AST遍历和IR生成
2. 函数声明和函数体处理
3. 变量声明和赋值处理
4. 控制流语句处理
5. 表达式求值处理
6. 类型转换处理
7. 内存操作处理

4.4.2 优化策略

1. 常量折叠：编译时计算常量表达式
2. 死代码消除：移除不可达代码
3. 循环优化：循环展开、循环不变代码外提
4. 内联优化：函数内联展开
5. 内存优化：内存访问优化、内存分配优化

4.4.3 实现要点

1. AST到LLVM IR的转换

2. 函数调用和函数声明处理

3. 内存管理机制

4. 异常处理机制

5. 优化策略实现