从一个简单的例子开始

    -- test/hello.gafq
    a = ("aaa" == "aaa")

从这个例子,我们知道a的结果是true

lua是如何判断字符串相等的呢?带着这个问题我们来看代码

1. 首先是main入口,创建一个虚拟机,并保存参数”./test/hello.gafq “

// gafq.c

int main(int argc, char **argv)
{
    ...
    ...
    gafq_State *L = gafq_open(); // 创建一个lua虚拟机
    ...
    s.argv = argv; // 保存参数
    ...
    status = gafq_cpcall(L, &pmain, &s); // 执行调用
    ...
    ...
}

2. 从main来了之后会走到pmain方法,其中的handle_script会执行脚本

//gafq.c
static int pmain(gafq_State *L)
{
    ...
    s->status = handle_script(L, argv, script); // 这里执行文件内容

}

3. 从pmain过来的执行,这里做了加载脚本 test/hello.gafq 和执行脚本内容

//gafq.c
static int handle_script(gafq_State *L, char **argv, int n)
{
    ...
    status = gafqL_loadfile(L, fname);
    ...
    status = docall(L, narg, 0); // 这边执行了文件好像
    ...
}

4. handle_script看两步操作,第一步处理加载的文件gafqL_loadfile

//gauxlib.c
GAFQLIB_API int gafqL_loadfile(gafq_State *L, const char *filename)
{
    ...
    lf.f = fopen(filename, "r");
    ...
    // 这里会加载两种文件,可能是文本,也可能是二进制,二进制通过判断第一位与魔数是否相等
    if (c == GAFQ_SIGNATURE[0] && filename) // 魔数相等,是gafq的二进制文件
    ...
    // 处理加载的内容,根据上一步的是否二进制,选择不同的调用来解析内容对应这两个方法gafqU_undump : gafqY_parser
    status = gafq_load(L, getF, &lf, gafq_tostring(L, -1));
    ...
    ...
}

5. 解释文件内容,这里我们会做词法分析,将文本内容做成TOKEN,还会创建字符串

//gparser.c
Proto *gafqY_parser(gafq_State *L, ZIO *z, Mbuffer *buff, const char *name)
{
    struct LexState lexstate; //词法分析的结构体
    ...
    gafqX_setinput(L, &lexstate, z, gafqS_new(L, name));
    gafqX_next(&lexstate); // 读取第一个token
    ...
}

6. 从5过来,先看第一步lua是找到一个字符串对象,如果有就返回,如果么有就创建

TString *gafqS_newlstr(gafq_State *L, const char *str, size_t l)
{
    GCObject *o;
    unsigned int h = cast(unsigned int, l); /* seed */
    size_t step = (l >> 5) + 1;             // 如果字符串太长只哈希一部分
    size_t l1;
    for (l1 = l; l1 >= step; l1 -= step) // 计算哈希
        h = h ^ ((h << 5) + (h >> 2) + cast(unsigned char, str[l1 - 1]));
    for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)]; o != NULL; o = o->gch.next)
    {   // 根据前面计算的哈希,从全局的字符串池子中取出字符串对象.如果有找到哈希值一样,长度一样,并且比较是一样的,就返回那个对象,如果没找到就创建个新的
        TString *ts = rawgco2ts(o);
        if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0))
        {
            /* string may be dead */
            if (isdead(G(L), o))
                changewhite(o);
            return ts;
        }
    }
    return newlstr(L, str, l, h); /* not found */
}

7. 第6步如果在全局的strt中的hash没找到字符串会创建新的字符串,然后放入全局的strt 中 hash

// gstring.c
static TString *newlstr(gafq_State *L, const char *str, size_t l, unsigned int h)
{
    TString *ts;
    stringtable *tb;
    if (l + 1 > (MAX_SIZET - sizeof(TString)) / sizeof(char))
        gafqM_toobig(L);
    ts = cast(TString *, gafqM_malloc(L, (l + 1) * sizeof(char) + sizeof(TString)));
    ts->tsv.len = l;
    ts->tsv.hash = h;
    ts->tsv.marked = gafqC_white(G(L));
    ts->tsv.tt = GAFQ_TSTRING;
    ts->tsv.reserved = 0;
    memcpy(ts + 1, str, l * sizeof(char));
    ((char *)(ts + 1))[l] = '\0'; /* ending 0 */
    tb = &G(L)->strt;
    h = lmod(h, tb->size);
    ts->tsv.next = tb->hash[h]; /* chain new entry */
    tb->hash[h] = obj2gco(ts);
    tb->nuse++;
    if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT / 2)
        gafqS_resize(L, tb->size * 2); /* too crowded */
    return ts;
}

8. 回到第五步中的

//gparser.c
Proto *gafqY_parser(gafq_State *L, ZIO *z, Mbuffer *buff, const char *name)
{
    struct LexState lexstate; //词法分析的结构体
    ...
    gafqX_setinput(L, &lexstate, z, gafqS_new(L, name));
    gafqX_next(&lexstate); // 读取第一个token 这里是词法分析读取第一个token
    // 在我们的例子中 a = ("aaa" == "aaa"), 读出a,返回这个是一个变量名TK_NAME,实现过程看第9步
    ...
}

9. 在第八步中,我们读取token判断a是一个变量,他的token是TK_NAME

// glex.c
static int glex(LexState *ls, SemInfo *seminfo)
{
    gafqZ_resetbuffer(ls->buff);
    for (;;)
    {
        switch (ls->current)
        {
            ...
        default:
        {
            if (isalpha(ls->current) || ls->current == '_')
            {
                /* identifier or reserved word */
                TString *ts;
                do
                {
                    save_and_next(ls);
                } while (isalnum(ls->current) || ls->current == '_');
                ts = gafqX_newstring(ls, gafqZ_buffer(ls->buff), gafqZ_bufflen(ls->buff));
                // 判断这个字符是一个关键字例如 and,do,local 还是一个变量名
                if (ts->tsv.reserved > 0)
                    return ts->tsv.reserved - 1 + FIRST_RESERVED;
                else
                {
                    seminfo->ts = ts;
                    return TK_NAME;
                }
            }
            ...
        }
        }
    }
}

10. 读取到第一个token后继续第5步的代码

//gparser.c
Proto *gafqY_parser(gafq_State *L, ZIO *z, Mbuffer *buff, const char *name)
{
    struct LexState lexstate; //词法分析的结构体
    ...
    gafqX_setinput(L, &lexstate, z, gafqS_new(L, name));
    gafqX_next(&lexstate); // 读取第一个token 这里是词法分析读取第一个token
    // 在我们的例子中 a = ("aaa" == "aaa"), 读出a,返回这个是一个变量名TK_NAME,实现过程看第9步
    chunk(&lexstate);
    ...
}

11. 新的chunk

//gparser.c
// 这里是解析代码块?
static void chunk(LexState *ls)
{
    while (!islast && !block_follow(ls->t.token))
    {
        islast = statement(ls); // 这里会根据前面读取的第一个token解析是
        ...
    }
}

// 11.1 解析代码块,在我们的上一步得到a的token是个变量名, 那么在这里认为他接下去应该是什么东西?
// 例如 a = ("aaa" == "bbb")
// 调用方法 a = function_name()
// a.a 取值
// a[] 取值
// a:a 函数
static int statement(LexState *ls)
{
    switch (ls->t.token)
    {
    ...
    default:
    {
        exprstat(ls);
        return 0; /* to avoid warnings */
    }
    }
}

//11.2
static void exprstat(LexState *ls)
{
    primaryexp(ls, &v.v);
}
/11.3
static void primaryexp(LexState *ls, expdesc *v)
{
    /* primaryexp ->
          prefixexp { `.' NAME | `[' exp `]' | `:' NAME funcargs | funcargs } */
    FuncState *fs = ls->fs;
    prefixexp(ls, v);
}

//11.4现在是TK_NAME
static void prefixexp(LexState *ls, expdesc *v)
{
    /* prefixexp -> NAME | '(' expr ')' */
    switch (ls->t.token)
    {
    case TK_NAME:
    {
        singlevar(ls, v);
        return;
    }

    }
}
//11.5
static void primaryexp(LexState *ls, expdesc *v)
{
    /* primaryexp ->
          prefixexp { `.' NAME | `[' exp `]' | `:' NAME funcargs | funcargs } */
    FuncState *fs = ls->fs;
    prefixexp(ls, v);
    for (;;)
    {
        switch (ls->t.token)
        {
        ...
        default:
            return;
        ...
        }
    }
}

//11.6
static void exprstat(LexState *ls)
{
    primaryexp(ls, &v.v);
    assignment(ls, &v, 1);
}

//11.7 从exprstat来, 这里是计算变量赋值表达式
static void assignment(LexState *ls, struct LHS_assign *lh, int nvars)
{
    ...
    if (testnext(ls, ','))
    {
        ...
    }
    else
    { /* assignment -> `=' explist1 */
        int nexps;
        checknext(ls, '='); // 检查a后面是不是有=号
        nexps = explist1(ls, &e);
        ...
    }
    ...
}

//11.8解析参数列表?
static int explist1(LexState *ls, expdesc *v)
{
    /* explist1 -> expr { `,' expr } */
    int n = 1; /* at least one expression */
    expr(ls, v);
    while (testnext(ls, ','))
    {
        gafqK_exp2nextreg(ls->fs, v);
        expr(ls, v);
        n++;
    }
    return n;
}

//11.9
在explist1中调用expr 相当于调用了 subexpr 方法
** subexpr -> (子表达式 | 一元运算符和子表达式) { 二元运算符和子表达式 }
** where `binop' is any binary operator with a priority higher than `limit'
static BinOpr subexpr(LexState *ls, expdesc *v, unsigned int limit)
{
    BinOpr op;
    UnOpr uop;
    enterlevel(ls);
    uop = getunopr(ls->t.token);
    if (uop != OPR_NOUNOPR)
    {
        ...
    }
    else
        simpleexp(ls, v);
}

//11.10
static void simpleexp(LexState *ls, expdesc *v)
{
    // 这时候解析到 ls->t.token = '('
    switch (ls->t.token)
    {
    default:
    {
        primaryexp(ls, v);
        return;
    }
    }
    gafqX_next(ls);
}

//11.11这边处理 ls->t.token == '(' 之后的解析
static void primaryexp(LexState *ls, expdesc *v)
{
    prefixexp(ls, v);
}

//11.12
static void prefixexp(LexState *ls, expdesc *v)
{
    /* prefixexp -> NAME | '(' expr ')' */
    switch (ls->t.token)
    {
    case '(':
    {
        // 匹配到时(,开始做下一步解析
        gafqX_next(ls); // 这里做了取下一步token, 在我们的例子后(之后是字符串 "aaa"
        expr(ls, v);

    }
    }
}

//11.13 前面我们遇到token = '('之后解析下一层又是subexpr
static BinOpr subexpr(LexState *ls, expdesc *v, unsigned int limit)
{
    BinOpr op;
    UnOpr uop;
    enterlevel(ls);
    uop = getunopr(ls->t.token); // 前面做了gafqX_next,这里token变成了286既TK_STRING
    if (uop != OPR_NOUNOPR)
    {
        ...
    }
    else
        simpleexp(ls, v); // 这里做了创建"aaa"字符串,然后又取下一个token
    op = getbinopr(ls->t.token); 这时候token变成了280 "==" 既 TK_EQ
    while (op != OPR_NOBINOPR && priority[op].left > limit)
    {
        expdesc v2;
        BinOpr nextop;
        gafqX_next(ls); // 这里又取了下一个token, a = ("aaa" == "aaa")这时候token变成下一个字符串"aaa"
        gafqK_infix(ls->fs, op, v);
        /* read sub-expression with higher priority */
        nextop = subexpr(ls, &v2, priority[op].right);
}

//11.14 由于前面 == 后取到了字符串"aaa"又递归进了这个函数
static BinOpr subexpr(LexState *ls, expdesc *v, unsigned int limit)
{
    BinOpr op;
    UnOpr uop;
    enterlevel(ls);
    uop = getunopr(ls->t.token);
    if (uop != OPR_NOUNOPR)
    {
        ...
    }
    else
        simpleexp(ls, v);
    /* expand while operators have priorities higher than `limit' */
    op = getbinopr(ls->t.token);
    // 最后一个aaa后这行就没有表达式了
}

//11.15 解析完后 我们又回到了11.12匹配到'('的地方继续往下判断
static void prefixexp(LexState *ls, expdesc *v)
{
    /* prefixexp -> NAME | '(' expr ')' */
    switch (ls->t.token)
    {
    case '(':
    {
        int line = ls->linenumber;
        gafqX_next(ls);
        expr(ls, v);
        check_match(ls, ')', '(', line); // 是不是括号匹配
        return;
    }
}

//11.16从11.15返回后回到了原本11.11的地方
static void primaryexp(LexState *ls, expdesc *v)
{
    prefixexp(ls, v);
     for (;;)
    {
        switch (ls->t.token) // 以为我们的例子代码就1行,前面解析完了之后,已经结束了,这里的token变成287,既 TK_EOS
        {
        default:
            return;
        }
    }
}

//11.17 从11.11一直返回到11.7的地方
static void assignment(LexState *ls, struct LHS_assign *lh, int nvars)
{
        // 我们从11.7-11.17做了解析,把我们一行的代码 a = ("aaa" == "aaa")解析完成, 这时候nexps = 1
        nexps = explist1(ls, &e);
        if (nexps != nvars)
        {
            adjust_assign(ls, nvars, nexps, &e);
            if (nexps > nvars)
                ls->fs->freereg -= nexps - nvars; /* remove extra values */
        }
        else
        {
            gafqK_setoneret(ls->fs, &e); /* close last expression */
            gafqK_storevar(ls->fs, &lh->v, &e);
            return; /* avoid default */
        }
    }
    init_exp(&e, VNONRELOC, ls->fs->freereg - 1); /* default assignment */
    gafqK_storevar(ls->fs, &lh->v, &e);
}


12. 解析文本的部分先告一段落,接下来看如何执行,回到第4步的handle_script中

//gafq.c
static int handle_script(gafq_State *L, char **argv, int n)
{
    ...
    status = gafqL_loadfile(L, fname); // 解析文本内容,在前面解析的*gafqY_parser中 中,我们弄出了struct FuncState funcstate;,这里要执行这个函数
    ...
    status = docall(L, narg, 0); // 这边执行了文件好像
}

13. 在上一步,我们做出的funcstate,于是docall会调用执行lua的方法

gdo.c
// 普通调用函数
void gafqD_call(gafq_State *L, StkId func, int nResults)
{
    ...
    if (gafqD_precall(L, func, nResults) == PCRGAFQ) // 如果是个lua的函数,会执行下面这一个方法
        gafqV_execute(L, 1);                       
    ...
}

14. 执行刚刚11解析出文本的内容

void gafqV_execute(gafq_State *L, int nexeccalls)
{
    ...
    pc = L->savedpc;
    ...
    for (;;)
    {
        //取出当前指令
        const Instruction i = *pc++;
        StkId ra;
        ...
        ra = RA(i); // 取出执行的A寄存器
        ...
        // 这里的i为 2,160,083,031
        // 对应二进制 1000 0000 1100 0000 0100 0000 0101 0111
        switch (GET_OPCODE(i))
        {
            // 计算相等
            case OP_EQ:
            {
                //条件成立就执行,否则就跳转equalobj是类型比较,相同类型用gafqV_equalval
                TValue *rb = RKB(i);
                TValue *rc = RKC(i);
                Protect(if (equalobj(L, rb, rc) == GETARG_A(i)) dojump(L, pc, GETARG_sBx(*pc));) pc++;
                continue;
            }

        }
    }
}

15.在14中运用到了三个宏

第一个宏GET_OPCODE(i)
    #define GET_OPCODE(i) (cast(OpCode, ((i) >> POS_OP) & MASK1(SIZE_OP, 0)))
    cast强制类型转换,把后面的值转成前面的类型
    OpCode 是enum常量
    MASK1(n, p) 创建在p位置开始创建n个为1的bit
    #define SIZE_OP 6  // 操作码大小占用6个比特
    MASK1(SIZE_OP, 0) = 二进制0000000000000000111111 = 十进制的63
    这里的i为 2,160,083,031
    对应二进制 1000 0000 1100 0000 0100 0000 0101 0111
    #define POS_OP 0                  // 操作码开始
    010111 & 111111 = 23 既OP_EQ

第二个宏RKB(i)
#define RKB(i) check_exp(getBMode(GET_OPCODE(i)) == OpArgK, ISK(GETARG_B(i)) ? k + INDEXK(GETARG_B(i)) : base + GETARG_B(i))

    这里的i为 2,160,083,031
    B         C          A       操作码EQ
    100000001 100000001 00000001  010111

    check_exp(c,e) 检查c 是不是true, 然后会返回e?
    #define getBMode(m) (cast(enum OpArgMask, (gafqP_opmodes[m] >> 4) & 3)) // 操作数B的使用模式
    cast强制类型转换,把后面的值转成前面的类型
    OpArgMask 是 enum常量
    gafqP_opmodes 是一个整数指令表,OP_EQ的整数是opmode(1, 0, 3, 3, 0)
    #define opmode(t, a, b, c, m) (((1) << 7) | ((0) << 6) | ((3) << 4) | ((3) << 2) | (0))
                                   (1000 0000) | (0)        | (0011 0000) | (0000 1100) | 0
    这里我们得到OP_EQ 在gafqP_opmodes[23] 的操作指令是二进制 10111100 为十进制的188
    所以 (gafqP_opmodes[m] >> 4) & 3) = ((188 >> 4) & 3)  = 3,转成OpArgMask常量为 OpArgK
    这里完成了宏RKB(i)的前半部 getBMode(GET_OPCODE(i)) == OpArgK 是true
    接下来看后半部
    ISK(GETARG_B(i)) ? k + INDEXK(GETARG_B(i)) : base + GETARG_B(i)
    这里看出是一个三元表达式
    #define GETARG_B(i) (cast(int, ((i) >> POS_B) & MASK1(SIZE_B, 0)))
    POS_B = (6(op操作码位数) + 8(A操作码位数) ) + 9(C操作码位数) = 23
    SIZE_B = 9
    得到B操作码是 100000001
    #define BITRK (1 << (SIZE_B - 1)) 1表示在常量位置, 0表示在寄存器*/
    #define ISK(x) ((x)&BITRK)     /* 看是存在常量还是寄存器 */
    我们的B操作码是 100000001 最高位是1,表示在常量位置,执行 k + INDEXK(GETARG_B(i))
    #define INDEXK(r) ((int)(r) & ~BITRK) // 获取常量的索引
    我们的 B操作码去掉最高位就是 00000001
    这里的k是
    Proto中的 TValue *k;函数使用的常数

第三个宏RKC原理类似RKB

16. 经过15的分析,我们回到14步中,我们获得了两个字符串对象,进入了我们问题的关键处,字符串是如何比较的

//gvm.c
// 计算相等
    case OP_EQ:
    {                       在我们的例子中 "aaa" == "bbb"
    TValue *rb = RKB(i);    // 获得了b操作符的字符串对象
    TValue *rc = RKC(i);    // 获得了c操作符的字符串对象
    Protect(if (equalobj(L, rb, rc) == GETARG_A(i)) dojump(L, pc, GETARG_sBx(*pc));) pc++;
    }

17. lua开始比较两个对象rb,和rc

#define equalobj(L, o1, o2) (ttype(o1) == ttype(o2) && gafqV_equalval(L, o1, o2))
lua会先比较类型,在比较数据,我们的例子,类型都是字符串是一样的
int gafqV_equalval(gafq_State *L, const TValue *t1, const TValue *t2)
{
    const TValue *tm;
    gafq_assert(ttype(t1) == ttype(t2));
    switch (ttype(t1))
    {
    '''
    '''
    -- 因为我们的例子是字符串,所以进入的default的分支
    default:
        return gcvalue(t1) == gcvalue(t2);
    }
}

    #define gcvalue(o) check_exp(iscollectable(o), (o)->value.gc)
    -- 从这个宏我们可以看出,当我们在比较字符串的时候,判断是不是同一个gc对象
    typedef union
    {
        GCObject *gc; // 间接引用
        void *p;
        gafq_Number n;
        int b;
    } Value;
    // 所有可回收的对象
    union GCObject
    {
        GCheader gch;
        union TString ts;
        union Udata u;
        union Closure cl;
        struct Table h;
        struct Proto p;
        struct UpVal uv;
        struct gafq_State th; /* thread */
    };

18. 至此我们知道了,lua会将字符串存在全局的strt中,比较的时候是比较是不是同一个gc对象

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注