loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

#

实现一种解释性脚本语言(三)

author: Kevin Lynx email: zmhn320#163.com date: 3.7.2009

词法分析

    词法分析属于整个编译流程中的第一个阶段。为什么要把编译过程分为多个阶段,这就
如同软件分层一样,个人觉得是出于降低复杂性的考虑。
    再次声明我不会告诉你任何编译原理的理论知识,因为坦率地说我也不会:D。所以我努
力将我们需要了解的概念尽可能简单地告诉你。当然,可能会与教科书不吻合。

什么是词法分析?

    词法分析就是把一段话整理成单词集合。举个简单的例子,例如有代码:age = age + 1;,
经过词法分析后,将得到:age、=、age、+、1、;几个符号。为了方便,我称每个单词为一
个token。

词法分析的作用

    词法分析分析出来的单词集合,直接作为编译流程中接下来的语法分析的输入。那么语
法分析阶段面对的将是一个一个的token,而不是单个的字符。
    例如,在处理age = age + 1;这种语句时,当我们获取到token "="时,我们直接期望接
下来的token应该是个表达式。以单词为单位地处理,比直接处理单个字符简单很多。

词法分析的过程

    词法分析的输入是单个字符流,一般我们fopen一个源代码文件,保存在一个char缓存
里,这就是词法分析的输入。而词法分析的最终输出结果就是一个一个的token。
    为了处理方便,token并不是单纯的单词。通常我们会将源代码中的所有单词分类,例
如变量名其实都属于一类token。简单的token可定义为:
    struct Token
    {
        int type;
        char value[256];
    };
    type用于表示token的类型,例如一个变量名token的类型是一个标识符。value可以用
来具体地保存这个变量的名字。

    对于type的处理,通常会事先定义一组枚举值,例如:
    enum    {    ID, NUM, STRING, IF, ELSE, WHILE, RETURN, FUNCTION }等等用于标示
在一个源代码中可能出现的所有token。

    虽然说词法分析的结果是一个token集合,但事实上我们并不是一次做完词法分析。通常
词法分析模块提供一个get_token函数。每次调用该函数时,都返回源代码中下一个token。
例如,有源代码:age = age + 1;
    第一次调用get_token将获得 { ID, "age" },第二次获得 { ASSIGN, "=" },第三次
获得{ ID, "age" },等等。

    那么,词法分析该如何实现?也就是struct Token get_token()函数如何实现?其实很
简单,你告诉我:给你一个字符串,你如何判断这个字符串全部是数字?
    int is_num( const char *str )
    {
        while( *str != 0 )
        {
            if( !isdigit( *str++ ) ) return 0;
        }
        return 1;
    }
    所以,基本上,词法分析的过程也就是这个过程。就拿标识符举例,典型的标识符一般
以字符开头,然后接着是数字或字符或_,当遇到非法字符时,这个标识符的扫描即结束。
    词法分析一般是个while+switch:
    struct Token get_token()
    {
        while( current_char != 0 )
        {
            switch( current_char )
            {
                case CHARACTER:
                    /* 扫描一个标识符 token */
                    break;

                case '=':
                    /* 获得一个 ASSIGN token */
                    break;

                    ...
            }
        }
    }

    现在,试着去总结一门语言里的每一个token的规则,然后自己去写写看。

代码导读

    在本节我将提供kl在googlecode的SVN上的代码,先不要去管代码包中的其他东西。关于
词法的代码可以在kllex.c kllex.h中找到。lex_token是提供给其他模块的接口,用于获取
当前扫描的token。扫描结果可以通过lexState结构体获取。
    再次提下版权问题,代码文件以及代码包中我并没有加入任何版权说明,哪怕是GPL。
但是如同我之前说的一样,我不介意你传播、改动此代码,但是请保留原作者信息。当然,
我并不介意你加上@modified by xxx:)。

    下载kl源代码:http://klcommon.googlecode.com/files/kllan_0.1.0.zip

posted @ 2009-03-07 13:43 Kevin Lynx 阅读(3775) | 评论 (2)编辑 收藏

实现一种解释性脚本语言(二)

author: Kevin Lynx email: zmhn320#163.com date: 3.6.2009

语言特性

    在正式讨论实现细节前明确下这个脚本语言的一些语言特性,基本上可以让我们预见将
来会遇到哪些难题。总的来说,它(脚本)将同我们平时接触的如lua一样的脚本语言:拥
有一般的编程语言特性,如变量、各种控制流程、也许还有函数,另一方面它还应该和它的
宿主语言结合,如作为一个库被用进C,这还涉及到给这门语言设计一种插件方式,最好能
通过独立的解释程序让脚本载入一些插件运行。

    以下在描述我写的这个脚本语言时,将以kl表示它的名字,以方便描述。

代码块:

    首先从整体风格上,kl如同C语言一样被划分为函数块,如:
    function func1()
    {
    }
    function func2()
    {
    }
    ...
    kl支持以{}隔离代码块,但是这并不意味着kl有多个独立的局部堆栈,如同C语言一样。
这些细节暂不讨论。本节描述的所有内容你都不必深究,因为我只要求你对kl有个感性上的
认识。
    函数块之外没有可执行的语句(statement)。那么你可能会想到程序的入口点也许会是
main。事实上从kl提供的库来看,并没有这种硬性要求。但是,kl的独立解释程序是这样要
求的。   

变量:

    kl允许你在任何地方使用一个变量。变量不需要事先定义,任何地方出现一个合
法的标识符时,就意味着kl内部会增加这个变量,并给予初值。变量也没有静态类型,也不
会固定为某一类型。就一门最简单的语言来看,我觉得数据类型无非就是字符串和数字类型

    所以,kl的变量在某一时刻必然是数字,或者字符串。在脚本里,你无法获知一个变量
的类型,事实上也没这个必要。说变量拥有一个类型属性,倒不如说值(value)有一种类型
属性。
    当字符串值与数字值参与运算时,如1+"a",其运算结果将自动转换为字符串,也就是
"1a"。
    一个只有标识符的语句(statement)通常意味着你想定义一个变量。这种无聊的手段通
常被用于定义全局变量。

运算符:

    kl支持一般的C语言风格的算术、比较、逻辑运算符。例如加减乘除、大于小于、逻辑
与逻辑或。

作用域:

    kl脚本里只有两个作用域:全局的和局部的。
    位于所有函数块外的变量处于全局作用域;位于函数内的变量处于局部作用域,位于函
数块内的代码块变量,还是处于局部作用域。
    当局部作用域内出现一个全局里的同名变量时,优先取局部作用域里的变量。这同C语
言一样。

控制语句if:
    if的语法同C语言一样,如:
    if( a > 10 )
    {
    }
    else
    {
    }
    if( a > 10 )中的a>10被我成为条件语句,所有条件语句,包括下面的while,都不能
为字符串。例如if( "a" )将被视为非法语句。(我为什么要这样考虑?- -!)

控制语句while:

    c-like while:
    while( a > 10 )
    {
    }
    很遗憾,我暂时没有加入对for的支持。因为我觉得既然有了while,有了循环控制,在
没有更多无聊时间的前提下,我没有必要加入for。

函数:

    很遗憾,函数的定义和调用和C语言有点不一样。这是因为kl没有变量类型,那就意味
着函数定义如果和C语言一样,就会出现语法歧义,如:
    func( a )
    {
    }
    就会和函数调用func(a)出现混淆。所以,我加入了function关键字。定义函数的语法
为:
    function func( a, b )
    {
    }
    如你所见,函数支持参数传递,当然也支持return a;返回值。kl是简陋的,因为它没
有指针之类的概念,所以你无法为函数传递一块数据。当然,kl也不能像lua一样让函数可
以返回多个值。
    函数调用的语法相对熟悉:
    func( 1, 3 );

数组:

    从一开始我就没考虑为kl加入数组。事实证明加入数组是一个不明智的做法。数组的支
持让代码在很多地方变得脏乱。无论如何,kl后来支持一维数组了。为了让代码保持那么一
点点的干净,我甚至为定义数组加入dim的关键字。这意味着,在kl里,数组和一般的变量
总有点不一样:变量无需定义,数组却必须事先定义。
    数组的长度不支持动态扩充。如果支持,我得让kl内部更好地去管理内存。
    数组元素的类型没有硬性的规定,这意味着a[0] = 1; a[1] = "a";是允许的。

    语言特性上就描述这些,在本节末尾我决定贴一段kl计算阶乘的代码:

/* fac.kl */
function main()
{
    n = input( "%d" );
    print( "fac(" + n + ") = " + fac( n ) );
}

function fac( n )
{
    if( n == 1 )
    {
        return 1;
    }
    else
    {
        return fac( n - 1 ) * n;
    }
}

posted @ 2009-03-06 16:01 Kevin Lynx 阅读(4666) | 评论 (9)编辑 收藏

实现一种解释性脚本语言(一)

author: Kevin Lynx email: zmhn320#163.com date: 3.6.2009

    (相信我,这一节全是废话。)
    我不是标题党,但是有必要解释下这个标题。综合来说我就是想与你分享我所学到的。
我会将我实现的这个简单的脚本语言的实现细节展示给你。它将涵盖:词法分析、语法分析
、符号表管理、语法树解释执行、插件管理等内容。
    我并不擅长传授编译原理知识。我没有听过编译原理课,所以我也不会编译原理(也许
即使我听了也不会:D)。所以对于这方面的能手而言,我口中的‘DFA‘可能会贻笑大方。
    显然,CPPBLOG上有编译原理上的大牛。如果你想学习更深入的知识,可以去请教他们。
vczh(http://www.cppblog.com/vczh/) 看起来是我所说的这个人。在致谢名单里我将真诚地
写上他的名字。他的’手把手xxx脚本‘系列多多少少还是给了我一些有用的信息。
    其次是FOX,在词法分析的DFA和NFA那里我请教了他一些问题。虽然我现在又忘了。如
你们所知,理论和实现之间总会隔着鸿沟。

    推荐《编译原理与实践》(<Compiler Construction:Principles and Practice>
Kenneth C. Louden)这本书。在你将来阅读我的脚本语言的实现代码时,你会发现有很一些地
方同这本书里的TINY语言实现代码有相似之处。建议你阅读TINY的代码。
    感谢VIM、GCC、GDB、MingW,我用这些软件在工作之余写出了这个东西的几千行C代码。
很明显我是个开源文化的爱好者。但是我不会告诉你unix有多么多么好,因为我也是个初学
者,我还不懂unix。开源在我看来更是一种分享知识的精神。让这种精神如同GPL一样病毒
式地传染下去。
    还有版权问题。但也许它不是个问题。我不会添加任何版权信息。我允许你任意传播、
改动我所散播的东西,但是唯一的基本条件是:保留作者的信息---不要告诉别人,这东西
是你做的。

    在所有的文章发布后,我都可能会再次修改。也许通过RSS或者日志日期之类你可以获
得修改提醒。

posted @ 2009-03-06 15:58 Kevin Lynx 阅读(6454) | 评论 (4)编辑 收藏

玩了一下alienbrain的EventsScript

从我接触的UNIX文化中我知道,要学会更好地去使用工具去组合工具来完成日常的工作。项目使用alienbrain作为源代码管理工具。每次在VC里有些代码文件里总会写些并不想签入到代码服务器上的代码,例如我经常#include "vld.h"来检测内存泄漏。但是真的等到签入代码时,又经常忘记删除这些代码。

 

于是我想,如果每次在我签入代码前,VC或者alienbrain或者其他工具能根据我的设置检查我的代码中是否存在这种不想签入的代码,然后提示我。问了一下向来很熟悉工具的FOX(很抱歉,我甚至不会使用WORD,我真不敢相信我的坦率:D),结果他也不知道。今天闲来无事翻了下alienbrain附带的文档,发现EventsScript。

 

alienbrain里的EventScript总的来说是一种让用户定制更多功能的机制。它定义诸如签入签出获取版本等动作为event,然后用户可以使用alienbrain支持的VBScript和JavaScript脚本来处理这些事件。例如,当你签出一个文件时,ab(alienbrain)会调用你的脚本,让你来处理这一事件)。当脚本返回时,ab继续处理刚才的操作(如果你实在想中止这一动作也可以)。

 

这正是我需要的一种机制。迅速地看完了EventScript这一节的文档。再想想我的需求,大体思路就是:给check in挂个脚本,让该脚本调用一个外部程序,处理将要check in的文件,分析这个文件。我可以规定在我的代码中凡是不想签入的代码都可以附加一个tag,例如:#include "vld.h" //DUMMY,分析该代码文件时,发现代码中有//DUMMY字符串,就提示我说该代码文件有不想被签入的代码,位于某某行。

 

看来我似乎需要一个grep工具,万恶的是windows只有find。不过find基本可以满足我的需求,但是find的输出结果看起来并不是那么友好,并不是可以被另一个程序处理的格式。(linux下通过建立标准的输入输出格式,从而可以轻松地让多个程序协作起来更好地完成很多事)无论如何,我需要使用ab提供给我的接口来试验下我的想法。

 

然后噩梦开始了。先是发现NxNLauncher(ab提供的一个接口,大致是这样拼写的,现在机器上没ab)的Exec接口是异步执行进程,从而StdOut属性及ExitCode总是得不到正确的值。后来一不小心在ab的wiki上看到,说Exec有个隐藏参数,用来标识是同步执行进程还是异步执行,显然,这个隐藏参数undocumented。- -!

 

再然后是每次执行find后,find程序倒是被执行起来了,结果却崩溃了。万恶的是我执行其他程序却很正常。google了一下居然发现没人遇到这个问题。最近我的windows总是崩溃各种程序,visual stdio, word, find。但是,我并不打算自己写个find,即使是简化版的。于是我决定写个findwrapper,让ab来调用我自己写的程序,然后我这个程序调用find。然后为了搞定两个程序的通信,又想起了管道pipe。当然,这里的通信很简单,我只需要让find的输出重定向到我的findwrapper,然后我的findwrapper又会被重定向到ab,然后我的ab脚本就可以捕获这些输出,然后再分析这些输出就可以了。- -!

 

其实,最简单的解决方法,就是我自己写个撇脚的程序,自己去分析要签入的文件是否含有//DYMMY字符串。但是很显然,我更喜欢证明我最初的想法是否正确。

 

然后,在我的findwrapper里,再一次让find崩溃。经过几次试验,显然问题出在共享管道上。find和ping的不同在于,find可以从标准输入里获取输入,而ping只需要一个标准输出(也许还有stderr)。在CreateProcess里传入的startup info结构体里,需要提供标准输入、标准输出、及错误输出三个handle。显然,问题出在标准输入上,我提供了错误的值。按照一般的接口设计,我以为我如果不提供输入句柄,find就会忽略。但是find显然没那么聪明,或者说,find更喜欢直接*ptr = 10而不是if( ptr != 0 ) *ptr = 10。无论如何,当我把输入句柄填为输出句柄后,findwrapper可以捕获find的输出了,当然,find也不崩溃了。

 

我总觉得折腾windows api有点噩梦的感觉。我记得几年前刚学windows编程的时候很多函数总要试验很多次才能得到正确的结果,基本上我要尝试各个参数的诸多组合。这还不包括上下文的影响,你要RegisterClass出了问题,CreateWindow楞是不会给你一点点有意义的error code,OMG。

 

 

 

posted @ 2009-02-28 16:48 Kevin Lynx 阅读(2639) | 评论 (3)编辑 收藏

自己写内存泄露检测库

author: kevin lynx

这个内存泄露工具最基本的原理就是利用宏替换掉标准的malloc、free(暂不考虑其他内存分配函数,
如realloc、strdup),记录下每次内存分配和释放动作。因为宏的处理发生在预处理阶段,所以可以
很容易地用你自己的malloc函数替换掉标准的malloc。例如:

/* lib.h */
#define malloc my_malloc
#define free my_free 

/* lib.c */
/* disable these macro in this compile unit */
#undef malloc
#undef free 

static int count = 0

void *my_malloc( size_t size )
{
    
++count;
    
return malloc( size );
}
 

void my_free( void *a )
{
    
--count;
    free( a );
}
 


要使用以上代码,用户在使用时就需要包含lib.h,从而可以使用宏将用户自己写的malloc替换
为my_mallo。当程序退出时,如果count大于0,那么可以肯定的是有内存泄露。当然,如果
count为负数,则很可能对同一个指针进行多次free。

但是以上代码的功能太局限了。一个真正的内存泄露检测库(工具),至少需要报告泄露的代码
文件、函数、行数等信息。当然,如果能报告调用堆栈,就更好了。不过这就依赖于具体的平台,
需要使用特定的系统接口才可以获取出。

要实现以上功能也很简单,只需要在每次调用malloc的时候,通过编译器预定义宏__FILE__、
__LINE__、__FUNCTION__(__func__)就可以得到文件名、函数、行号等信息。将这些信息保存
起来,然后在free的时候移除相应的信息即可。

最简单的实现方式,就是保存一个表,表里记录着每次分配内存的信息:

 

struct memRecord
{
    
char file[MAX_FILE_NAME];
    
char func[MAX_FUNC_NAME];
    size_t lineno;
    
void *address;
    size_t size;
}


struct memRecord mem_record[MAX_RECORD]; 

 

但是,通过单单一个free函数的void*参数,如何获取出对应的分配记录呢?难道:

for( size_t i = 0; i < MAX_RECORD; ++ i )
{
    
if( address == mem_record[i].address ) 
    
{
        
/* shit */
    }

}
 

 

虽然可行,但是很stupid。这里提供一个小技巧:

 

void *my_malloc( size_t size )
{
    
void *= malloc( size + sizeof( size_t ) );
    
return (char*)a + sizeof( size_t );
}
 

void my_free( void *a )
{
    
/* actually, 'a' is not the real address */
    
char *= ((char*)a - sizeof( size_t ) );    
    free( p );
}

 

意思就是说,我多分配了4字节内存(sizeof( size_t ) ),用于保存这次分配记录在mem_record
中被保存的索引。在释放内存的时候,通过一些地址偏移计算,就可以获取出真正的系统malloc
返回的地址,从而安全释放(别给我说这里的计算存在平台和编译器的限制,没认真看文章的SB才说)。

另一个问题是,我们如何处理每次分配释放时,对于分配记录那个数据结构,也就是mem_record。
每一次free的时候,移除的记录可能位于mem_record的任何位置。一定时间后,mem_record内部
将出现很多漏洞(已经没用的数组位置)。解决这个问题最直接当然还是最stupid的方法,就是每次
free移除记录时重新整理一遍mem_record。如果你这样做了,那你的malloc/free比微软的还慢。

我的解决方法是:
size_t free_index[MAX_RECORD];
用于保存这些出现漏洞的index。每一次free移除记录时,就把这个记录对应的inex保存进来,表示
这个index指向的mem_record[]可用。每一次malloc的时候,先从这里取index,如果这里没有,那
可以直接从mem_record的末尾取。

具体细节就不阐述了,典型的空间换时间方法。整个库很简单,代码100来行。我也只进行过粗略的
测试。我肯定这100来行代码是有问题的,相信自己的代码存在问题是对bug的一种觉悟,哈哈哈。

这个东西只检测C语言的内存泄露,其实要检测C++的也很简单,只需要重载new和delete就可以了。

要放春节假了,在公司的最后几个小时实在无聊,才做了这个东西,前后花了1个多小时,写起来感觉
不错。

 

 

代码下载

 

posted @ 2009-01-23 17:43 Kevin Lynx 阅读(4364) | 评论 (5)编辑 收藏

小写了个XML解析器

    开始用FLEX做词法分析,然后在此基础上稍微做些符号匹配(实在称不上语法分析),即完成了XML
文件的简单解析。
    我把XML文件拆分成:<, >, />, </, =, ID, STRING 等token。这样一整理,用FLEX直接生成词法
分析程序。每一次getToken就返回这些token。上层的语法匹配就变得比较简单。例如当得到"/>"token
时,我就可以判断这是一个节点的结束;当得到ID token时,就可以推测下一个token为"=",再下一个
是个STRING。不过对于部分token,也需要做一两个token的回溯,例如当遇到"<"时,并不一定表示一个
新节点的开始,它可能是新节点的开始,同样也可能是上一个节点的结束("</")。
    以我薄弱的编译原理知识来看,解析XML变得非常容易。除此之外,还需要写一些上层代码来保存
XML结构,以方面更上层代码获取XML文件的配置信息。因为我打算用纯C来写这个东西,所以数据结构方
面只有自己处理。这里我以一种变相的树结构来保存:每一个节点有两个域:first child, sibling。
其实这样做是一个很明显的通用做法,因为XML种每一个节点都可能拥有不定数量的children节点,如果
让parent直接去保存,显然很笨。例如:
    <Resource>
        <bmp file="1.bmp"/>
        <bmp file="2.bmp"/>
    </Resource>
    可以使用这样的数据结构来存储:
    struct xmlNode
    {
        ...
        struct xmlNode *child;
        struct xmlNode *sibling;
    };
    对于Resource这个node而言,其child域指向第一个bmp节点(file属性为1.bmp那个节点);对于第一
个bmp节点而言,其sibling域则指向了第二个bmp节点。
    这个简单的xml解析器是在公司外网机器上写的,没有VC,没有任何IDE。代码我是用VIM敲的,敲好
后写makefile,用mingw里的gcc、make来生成程序,用gdb来调试程序。这算是第一次离开VC写的一个非
练习程序(起码用makefile来组织工程)。- -| makefile写的比较烂,gdb用得很不熟,不过好歹调试出来
了。越来越想换个平台,只可惜工作还是得在windows vc下,很扫兴。
    后来发觉词法分析也很简单,用FLEX的时候正则表达式都写出来了。前段时间一直在看编译原理,虽然不
用功。但是就这里而言,基本可以直接根据正则表达式画出DFA。终于不用接触那恶心的从NFA转DFA的
过程,因为我至今不会,更不会写代码转。- - 总而言之,自己手写了词法分析。边写边参考编译原理
与实践中附带的tiny-c编译器的词法分析部分,最终发现我抄了一遍。MD,一点技术含量都没有。

附上全部源代码(对于代码我还是比较满意的:D),下载

posted @ 2008-12-10 16:22 Kevin Lynx 阅读(4541) | 评论 (9)编辑 收藏

最近的两个问题:less for std::map,静态变量初始化顺序


说下最近自己遇到的两个值得让人注意的问题。
其一是关于自己给std::map写less predicate,std::map第三个参数是一个典型的functor。map内部将使用
这个functor去判定两个元素是否相等,默认使用的是std::less。但是为什么传入的是一个判断第一个参数
小于第二个参数的functor,而不是一个判断两个参数是否相等的functor?按照STL文档的说法,当检查两
个参数没有小于也没有大于的关系时,就表示两个参数相等。不管怎样,我遇到了需要自己写这个functor
的需求,于是:

struct MyLess
{
    bool operator() ( long left, long right )
    {
        //...
    }
};

DEBUG模式下编译没问题,RELEASE模式下却出现C3848的错误。这就有点奇怪了,如果确实存在语法错误,
那么DEBUG和RELASE应该一样才对。查了下MSDN,C3848的错误是因为const限定符造成的,如:

const MyLess pr;
pr(); // C3848

于是,在operator()后加上const,就OK了。看了下VC std::map相关代码,以为是DEBUG和RELEASE使用了不
同的代码造成。但是我始终没找到不同点。另一方面,就STL内部的风格来看,应该不会把predicator处理
成const &之类的东西,全部是value形式的。奇怪了。

第二个问题,涉及到静态变量。这个东西给我的印象特别深刻,因为以前去一家外企应聘时被问到,当时
觉得那个LEADER特别厉害。回来后让我反思,是不是过多地关注了C++里的花哨,而漏掉了C里的朴素?导致
我至今对纯C存在偏好。

说正题,我现在有如下的文件关系:

// def.h
struct Obj
{
    Obj()
 {
  ObjMgr::AddObj( id, this );
 }
 int id;
};

struct ObjMgr
{
    static void AddObj( int id, Obj *t )
 {
  ObjTable[id] = t;
 }
 static std::map<int, Obj*> ObjTable;
};

static Obj _t;

// ObjMgr.cpp
#include "def.h"

static std::map<int, Obj*>::ObjMgr ObjTable;

// main.cpp
#include "def.h"

这里举的例子可能有点不恰当,我在一台没有编译器的机器上写的这篇文章。忽略掉这些旁支末节。我的意思,
就是想让Obj自己自动向ObjMgr里添加自己。我们都知道静态变量将在程序启动时被初始化,先于main执行之前。

上面代码有两个问题:

一、
代码没有按照我预期地执行,如果你按照我的意思做个测试,你的程序甚至在进main之前就crash了。我假定你
用的是VC,因为我没在其他编译器上试验过。问题就在于,Obj的构造依赖于ObjTable这个map对象。在调试过程
中我发现,虽然ObjTable拥有了内存空间,其this指针有效,但是,map对象并没有得到构造。我的意思是,Obj
的构造先于ObjTable构造(下几个断点即可轻易发现),那么在执行map::operator[]时,就出错了,因为这个时候
map里相关数据还没准备好。

那是否存在某种机制可以手动静态变量的初始化顺序呢?不知道。我最后怎样解决这个问题的?

二、
在还没有想到解决办法之前(不改变我的设计),我发现了这段代码的另一个问题:我在头文件里定义了静态
变量:static Obj _t; 这有什么问题?想想预编译这个过程即可知道,头文件在预编译阶段被文本展开到CPP
文件里,然后,ObjMgr.cpp和main.cpp文件里都将出现static Obj _t;代码。也就是说,ObjMgr.obj和main.obj
里都有一个文件静态变量_t。

看来,在头文件里放这个静态变量是肯定不对的。于是,我将_t移动到ObjMgr.cpp里:

// ObjMgr.cpp
#include "def.h"

static std::map<int, Obj*>::ObjMgr ObjTable;
static Obj _t;

按照这样的顺序定义后,_t的构造居然晚于ObjTable了。也就是说,放置于前面的变量定义,就意味着它将被
首先构造初始化。这样两个问题都解决了。

但是,谁能保证这一点特性?C标准文档里?还是VC编译器自己?

 

 

 


 

posted @ 2008-11-11 17:55 Kevin Lynx 阅读(7306) | 评论 (13)编辑 收藏

让人无语的boost

    关于BOOST,撞车,严重撞车。每一次都让我有点无语。
    第一次是我所谓的宏递归,其实就是一个macro library,有一天就不小心在BOOST的library list上
看到了这个东西。当然,BOOST很牛,别人的这个macro是真的library。但是,我们的需求撞车,我们的
实现手段撞车。于是下定决心下次想要实现个什么东西的时候,先去看看BOOST,可以省掉不少脑力。
    本来就没有做好,何必吃力不讨好?
    第二次,当我写下类似的模板代码时:

    template <typename _Tp>
    
void func( _Tp t );


    我总要花掉几秒钟时间去决策func的参数是用_Tp&还是_Tp,也就是所谓的究竟是按值传送还是按引用
传送。如果按值传送,当_Tp为一个类时,复制的东西过多时,显然效率上过不去。作为func的实现者,良
心上更过不去。后来一想,STL的各种算法里到处都是按值传送,这样做总有它的理由吧?
    但是,这样做就是不够完美。
    于是想起了boost::ref。但是这个时候我并不知道boost::ref是个什么东西。我只是以前在各种地方
看到过这个东西。我还是决定自己实现一个。
    实现一个什么?考虑有:

    template <typename _Tp>
    
void func( _Tp t );


    而我这个时候要传递一个类对象过去CBaseObject obj。为了效率,我写下如下的代码:

    template <typename _Tp>
    
class ref_wrapper
    
{
    
public:
        ref_wrapper( _Tp 
&p ) : _obj( &p ) { }
        
operator _Tp& () return *_obj; }    
    
private:
        _Tp 
*_obj;
    }
;


    然后再使用func时,func( ref_wrapper<CBaseObject>( obj ) );这样,发生复制操作的最多就是这
个ref_wrapper,基本上也就是复制了一个指针,而不会复制整个obj。当然,这里可以写一个模板函数去
简化func的调用,如:

    template <typename _Tp>
    ref_wrapper
<_Tp> ref( _Tp &t )
    
{
        
return ref_wrapper<_Tp>( t );
    }


    这样调用的时候就简单了:func( ref( obj ) );
    其实这就是boost的ref库,按照其官方文档,ref库就是:
    The Ref library is a small library that is useful for passing references to function
templates (algorithms) that would usually take copies of their arguments.

    然后我就懵了。于是我不得不在kl_ref.h里写上check out boost::ref for more information的字眼。

    好,接下来说说第三次。
    第三次我遇到了这样一种需求,我需要一个容器,就像你知道的std::list。但是与std::list甚至STL
中所有容器都不同的是,这个容器里保存的东西具有不同的类型。
    这个时候我想起了tuple。我没有实现过tuple。大致上这个东西的实现原理就是利用类型递归来保存
数据,就像loki的type list。另一方面,tuple的尺寸似乎不能动态增长。
    于是我有了自己撇脚的实现:

 

    class base_type
    
{
        
virtual ~base_type() { }
    }
;
    template 
<typename _Tp>
    
class var_wrapper
    
{
    
public:
        var_wrapper( 
const _Tp &t ) : _t( t )  {}
        
operator _Tp& () return _t; }
    
private:
        _Tp _t;
    }
;   

    
class var_list
    
{
    
public:
        typedef std::vector
<base_type*> TypeList;
    
public:
        
        template 
<typename _Tp>
        
void add( const _Tp &t )
        
{
            var_wrapper
<_Tp> *var = new var_wrapper<_Tp>( t );
            _list.push_back( t );
        }
 

        template 
<typename _Tp>
        _Tp 
&get( size_t index )
        
{
            base_type 
*base = _list.at( index );
            typedef var_wrapper
<_Tp> var_type;
            var_type 
*var = static_cast<var_type*>base );
            
return *var;
        }

    
private:
        TypeList _list;
    }

 

    说白了,我就是利用一个包装类将各种类型包装其中,然后利用基类指针实现统一管理。直白地说,我
对这个组件不满意。让人诟病的是,get接口是类型不安全的。例如:

    int a; 
    CBaseObject obj;
    var_list my_var_list;
    my_var_list.add
<int>( a );
    my_var_list.add
<CBaseObject>( obj );


    取出值的时候:

    int b = my_var_list.get<int>0 );
    CBaseObject cobj 
= my_var_list.get<CBaseObject>1 );


    但是,因为get没有类型检查,即使你:

    CBaseObject cobj = my_var_list.get<CBaseObject>0 );


    也不会出错,编译器不会给予你警告。
    事情到此结束,这个类型不安全的组件只能依靠程序员自己的谨慎去生存。

    然后,又是一个不小心,我在boost里看到了any。boost::any库同boost::ref库一样,是一个tiny
library。几十行的代码一目了然。
    boost::any有一个placeholder基类,有一个template <typename ValueType> holder派生类,然后有
一个提供给外部的any类。看了代码后有一种让我喷血的感觉。其实现原理和我自己的完全一致。
    比较而言,我觉得我的var_list撇脚到了极致。因为我封装了容器,而这显然是没必要的,并且限制
了其使用范围。而boost::any则是仅仅封装了类型。
    数据转换方面,boost::any提供了any_cast和unsafe_any_cast。unsafe_any_cast和我这里用的转换
差不多,也就是我说的类型不安全。而他的any_cast呢?则是用到了typeid,多了次类型检查而已。
    没办法,看来var_list需要被删掉,直接搬boost::any过来吧,同样地check out boost::any for more
information...
    现在看来,boost真的很强大。我感觉再怎么偏门的需求,都能在boost里找到个实现。痛定思痛,决定
把boost doc长期开着。

posted @ 2008-10-15 11:23 Kevin Lynx 阅读(4704) | 评论 (10)编辑 收藏

代码自动生成-宏递归思想

Macro Recursion
author: Kevin Lynx

Preface

    本文可能是<代码自动生成-宏带来的奇技淫巧>的续写。我尽力阐述如何让宏递归(或者说重复)地有规律地产生一
些符号,而让我们少写很多重复代码,也许这些代码只有那么一点点的不同。将这项小技巧用于底层库的编写,会让代码
看起来干净不少,同时文件尺寸也会骤然下降。


Problem


    如果你曾经写过functor,那么你肯定对某些代码进行粘贴复制然后修改。更让人郁闷的是,这些代码基本是一样的。
例如,一个典型的functor可能为:

    template <typename Prototype>
    
class functor;
    template 
<typename R, typename P1>
    
class functor<R(P1)>;
    template 
<typename R, typename P1, typename P2>
    
class functor<R(P1,P2)>;


    //好,接下去你可能厌烦了,可能会复制一个带有两个参数的functor,然后修改为处理3个参数的。
    这只是一个很简单的问题。宏不是c++里的东西,本文自然也不是讨论各种花哨的模板技术的。如果我之前那篇关于
宏的文章只是让你去分析问题以及更深层次地认识宏,那么现在我将分享我的这部分思想给你。
    关于上面的问题,我们期待得到这样的解决方案:

    template <typename R, DEF_PARAM( 2 )>
    
class functor<R( DEF_ARG( 2 ) )>;


    那么,它将自动生成:

    template <typename R, typename P1, typename P2>
    
class functor<R(P1,P2)>


    也就是说,DEF_PARAM(n)这个宏将根据n值自动生成一串符号,例如DEF_PARAM(2)就生成typename P1, typename P2。
同样,DEF_ARG(n)也会根据参数生成类似于P1,P2,...,Pn的符号串。

思考

    仔细思考下,我们可以看出DEF_PARAM和DEF_ARG这样的宏具有一种递归的特性(其实说成重复可能更合适):每次展
开的内容基本一样,不断调用自身直到遇到终止条件。
    那么,我们的目标锁定于,用宏来实现递归。


Pre-Implement

    在开始之前,我需要告诉你一些基本的东西:
    在阅读一个宏时,你最好按照预处理的处理方式去逐个展开。当我说到展开时,我的意思是把宏替换为宏体。预处理器
展开宏的过程大致为:如果宏参数也是个宏,那么先将宏参数全部展开,再展开该宏;这个时候会扫描展开后的宏,如果
遇到其他宏,则继续展开。例如有一下宏:

 

#define PI 3.14
#define MUL_PI( n ) n * PI
#define TWO 2


    当我们写下MUL_PI( TWO )时,预处理发现MUL_PI的参数TWO 是个宏,那么先将TWO展开得到2,然后将2放进宏体展开
得到 2 * PI;预处理器对 2 * PI 进行扫描,发现还有宏PI,于是对PI做展开,得到 2 * 3.14。这个过程是递归的。
    但是也有例外,如果MUL_PI对宏参数进行了#或者##,那么该宏参数不会被展开。(参见以前那篇文章吧)
    任何时候,你可以通过以下宏去查看某个宏展开后的样子,可以方便你调试你的宏:

#define TO_STRING( x ) TO_STRING1( x )
#define TO_STRING1( x ) #x 


    (为什么要写个TO_STRING1,因为这是为了让x充分展开,避免上面提到的那个例外)   

    其他规则我会在文中需要的地方提出来。
实现

    就像大部分介绍递归函数时候给的例子,这里我也将阶乘作为例子。考虑如下典型的阶乘函数:

    int fac( int n )
    
{
        
if( n == 1 ) return 1;
        
return n * fac( n - 1 );
    }
 


    其核心部分在于 n * fac( n - 1 ),我们假设我们的宏也可以写成这样的的形式:

    #define FAC( n ) n * FAC( n - 1 )


    但是这样的宏是有问题的:
    当宏被展开时,如果遇到了自身,那么将被处理为一般符号,例如展开FAC( 3 )时,会遇到 FAC( 2 ),那么就把FAC
( 2 )中的FAC当成了一搬符号。
    这样的限制注定了我们无法让宏真正地调用自身来实现递归。于是,我们不得不写下以下丑陋的符号,从而去模拟递
归的每一次符号调用:

#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##(n-1)( n - 1 )
#define FAC_3( n ) n * FAC_##(n-1)( n - 1 ) 


    这系列宏有点别扭(如果你足够细心),因为我们明显知道FAC_2返回的将是2,而FAC_3返回的当时6。我们这里只是
模拟,同样,这使得我们可以把FAC_1作为递归的终止条件。
    我们的预想是,当调用FAC_3时,它把n-1的值2合并到FAC_中,从而调用FAC_2,以此类推。
    但是这依然有问题,编译器会提示‘找不到符号FAC_’。导致这个问题的原因在于:宏展开只是单纯的字符替换,是我们
想太多了,预处理器并不会去计算( n - 1 )的值是多少,也就是我们无法得到FAC_2这个宏。

    所以,FAC_3( 3 ) 会被初次替换为 3 * FAC_(3-1)( 3 - 1 )。这个时候编译器就把FAC_当成了一个普通符号。我们可以
自己定义个FAC_来证明这一点:

 

#define FAC_( n ) T 

 

    那么,FAC_3( 3 )就被替换为 3 * T(3-1)( 3 - 1 )。

    解决这个问题的办法关键在于,让预处理器自动计算出( n - 1 )。记住,我们解决问题的唯一办法是:字符替换。
所以,我们可以写下如下代码:

 

#define DEC_1 0
#define DEC_2 1
#define DEC_3 2 

#define DEC( n ) DEC_##n 

 

    通过,DEC( n )这个宏,我们可以获取到一个( n -1 )的数。例如,DEC( 3 )被替换为 DEC_3,继续替换为 2。

    于是,我们新的FAC系列宏变为:

 

#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##DEC( n )( n - 1 )
#define FAC_3( n ) n * FAC_##DEC( n )( n - 1 ) 

 

    不好意思,这样依然是不正确的!预处理器直接把FAC_和DEC( n )连接成符号了,而不是单个地先处理他们,最后再
合并他们。

    OK,先解决这个问题:先处理FAC_和DEC( n ),再合并他们,而不是先合并他们。要解决这个问题,可以通过第三个宏
来实现:

 

#define CHR( x, y ) x##y 

 

    作为连接两个符号为一个符号的宏,这个宏显然是不正确的,因为宏展开还有个规则:如果宏体对宏参数使用了#或##,
那么宏参数不会被展开,也就是说:如果CHR( FAC_, DEC( 3 ) 那么得到的只会是 FAC_DEC( 3 )。通常情况下我们是
再写个宏:

 

#define CHR( x, y ) CHR1( x, y )
#define CHR1( x, y ) x##y 

 

    从而可以保证在正式连接x和y前,x和y都被完全展开。

    这个时候,我们的FAC系列宏变为:

 

#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( n - 1 ) 

 

    结果呢?结果还是有问题。= =
    我们假设CHR( FAC_, DEC( n ) )已经真的按我们预想展开为 FAC_2了,那么FAC_3( 3 )会被展开为什么呢?
被展开为 3 * FAC_2( 3 - 1 )。这是错误的,传给 FAC_2 的参数是 3 - 1就意味着错误。我们又臆想预处理器会
帮我们计算 3 - 1的结果了。我们必须保证传给 FAC_2的参数是个数字2。解决这个问题的办法就是通过DEC(n)宏。

   于是,FAC系列宏变为:

 

#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) ) 

 

    这个时候,FAC_3( 3 )将会被替换为:3*2*1。这就是我们要的结果。

In practice

    以上只是向你展示一个过程,用宏去计算阶乘,就像用模板去计算阶乘(模板元编程)一样,只是一个用于展示的东西,
没有什么实际价值。接下来我们开始有实际的工作,完成之前的预想:

 

template <typename R, typename P1, typename P2, typename P3>
class functor<R (P1, P2, P3)> 

 

    直接:

 

template <typename R, PARAM( 3 )>
class functor<R (ARG( 3 ))> 

 

    先考虑PARAM宏,该宏的任务就是生成类似于:typename P1, typename P2, typename P3这样的符号。我们假象它每一次
递归都生成 typename Pn, 的字符串,那么当他递归完时,可能就生成typename P1, typename P2, typename P3, 结果
多了个逗号,也许最后一次结果不该有逗号。

    ARG宏和PARAM宏本质上相同,只是重复的符号不是typename Pn,而是Pn。

    最直接想到的是:

 

#define PARAM_1( n ) typename P##n
#define PARAM_2( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
#define PARAM_3( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n 

 

    结果我们得到了个错误的展开结果:
typename PDEC( 2 ),typename PDEC( 3 ),typename P3

    这个问题出在:PARAM_3( 3 )当替换为 PARAM_2( DEC( n ) )时,因为PARAM_2(n)宏对于宏参数n使用了##,也就是那个
typename P##n,所以这里不会把 DEC( n )展开,而是直接接到P后面。所以就成了typename PDEC( 3 )。

    为了消除这个问题,我们改进PARAM为:

 

#define TYPE( n ) ,typename P##n
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) ) 

 

    之所以加入TYPE(n),是因为 ,typename P##n 这个宏本身存在逗号,将其直接用于宏体会出现问题。

    于是,我们得到了正确的结果。

    其实,PARAM系列宏宏体基本是一样的,除了终止条件那个宏,为什么我们要写这么多呢?理由在于宏体不能自己调用
自己,所以才有了PARAM_3, PARAM_2。

    我们可以将上面的一系列宏抽象化,使其具有可复用性:

 

#define PARAM( n ) ,typename P##n
#define PARAM_END typename P 

#define ARG( n ) ,P##n
#define ARG_END P 

#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) ) 

#define REPEAT_1( n, f, e ) CHR( e, n )
#define REPEAT_2( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define REPEAT_3( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) ) 

#define DEF_PARAM( n ) REPEAT_##n( n, PARAM, PARAM_END )
#define DEF_ARG( n ) REPEAT_##n( n, ARG, ARG_END ) 

 

    我们创建了可重用的REPEAT系列宏,用于创建诸如typename P1, typename P2, typename P3或者P1,P2,P3之类的符号,
通过更上层的DEF_PARAM(n)和DEF_ARG(n),就可以直接创建出我们上面所需要的符号串,例如:

    DEF_PARAM( 3 ) 就得到 typename P1, typename P2, typename P3
    DEF_ARG( 3 ) 就得到 P1, P2, P3

More in practice

    下载中提供了我使用这个宏递归技术写的lua_binder(如果你看过<实现自己的LUA绑定器-一个模板编程挑战 >),你
可以与上一个版本做一下比较,代码少了很多。
    同样,我希望你也能获取这种宏递归的思想。   

相关下载

   使用宏递归的lua_binder

posted @ 2008-08-20 17:48 Kevin Lynx 阅读(12002) | 评论 (25)编辑 收藏

实现自己的LUA绑定器-一个模板编程挑战

     摘要: 实现LUA绑定器 author : Kevin Lynx Preface     当LUA脚本调用我们注册的C函数时,我们需要逐个地从LUA栈里取出调用参数,当函数返回时,又需要一个一个地往LUA栈压入返回值,并且我们注册的函数只能是int()(lua_State*)类型。这很不方便,对于上层程序员来说更不方便。    因此我们要做的...  阅读全文

posted @ 2008-08-13 09:33 Kevin Lynx 阅读(6865) | 评论 (15)编辑 收藏

仅列出标题
共12页: First 4 5 6 7 8 9 10 11 12