4.3 创建及使用存储信息的基本数据结构
4.3.1 创建及使用类信息表
在SOOL程序中规定只能在类中声明和实现函数,给函数发消息的时候一定标明给哪一个类的哪一个对象中的函数发消息,若该类的父类中有同名函数,以该类中的函数为准;若该类中无这一函数,而某个父类中有这一函数,向上查找,以最近的父类为准,由于SOOL语言中规定只能单继承,所以这里不存在歧义的问题.由此可知,类与函数关系密切,类变化会影响类中的函数,进而影响函数中的变量,影响程序执行路径上的条件表达式的值,因此必须创建和使用类信息表.
在SOOL语言中规定声明和实现必须在同一位置,不允许声明与实现分离即先声明后实现的情况.在语法树中类声明和实现处创建类信息表,填写类信息表结点结构中各项值:填写类名;把其指向父类的指针指向其父类,若其没有父类,则为NULL;把类中成员变量表的指针指向该类的成员变量表,同时填写类中成员变量表,成员变量表结点结构见前文,其中的变量信息表指针指向一个为该成员变量新建的变量信息表;把类中成员函数表的指针指向该类的成员函数表,同时填写类中成员函数表,成员函数表结点结构见前文,其中的函数信息表指针指向一个为该成员函数新建的函数信息表;把下一结点指针暂时置为NULL,当有下一个类出现时,指向下一个类结点,同时把上一个类信息表中的下一结点指针指向该类信息表.
在用类声明对象时,把类中所有成员变量,成员函数以及该类所有继承的父类中成员变量,成员函数拷贝一份给这个对象,这时就需查类信息表,查找所需信息用来填写该对象的对象生存期表.
4.3.2 创建及使用对象生存期表
一个类可以声明不同的对象,同一个类中的不同对象可以有不同的成员变量和成员函数,类发生变化时,类的对象一定发生变化;反之,对象发生变化时类不一定发生变化.在使用类中成员变量和成员函数时实际上是使用类的对象的成员变量和成员函数.对象与变量,函数发生直接联系,对象中的变量和函数发生变化,最终会影响程序执行路径上的条件表达式的取值,因此必须创建和使用对象生存期表.
在SOOL语法树中变量声明处,若声明的变量类型为类类型,也就是某一个类名时,被声明变量为一个对象,此时创建对象生存期表,填写对象生存期表结点结构中各项值:填写对象名;把类信息表指针指向拷贝给该对象的类信息表;把对象中的成员变量表指针指向该对象的成员变量表,同时填写对象中成员变量表;把对象中成员函数表的指针指向该对象的成员函数表,同时填写对象中成员函数表;把下一结点指针暂时置为NULL,当有下一个对象出现时,指向下一个对象结点,同时把上一个对象生存期表中的下一结点指针指向该对象生存期表.
在给对象中的成员函数发消息时,去查该对象的对象生存期表,对该函数影响到的成员函数和成员变量查对象生存期表中的成员函数表和成员变量表进行修改,同时对该对象的类信息表中的受到影响的部分进行修改;在使用对象中的成员变量时,若改变其值,去查该对象的对象生存期表,修改对象生存期表中的成员变量表中对应的项.
4.3.3 创建及使用变量信息表
在SOOL语法树中变量声明处创建变量信息表,填写变量信息表结点结构各项值:填写变量名;填写变量状态,变量状态共有四种:Unknown,Known,Input,Loop,它们表示变量为未知变量(U),已知变量(K),输入变量(I)和与循环有关的变量(L).这里的未知变量(U)的与前文中介绍的部分求值技术中未知变量的意义相同,所有变量的变量状态初始值为U;这里的已知变量(K)与前文中介绍的部分求值技术中的已知变量的意义相近,若一个变量被赋值或由于给类中成员函数发消息引起的隐式变量赋值,则该变量状态为K;这里的输入变量(I)表示一个变量是输入变量,这是我们生成测试用例所最需要的部分,在程序输入语句中的变量为输入变量,把变量状态位填写为I,同时填写输入变量表并把指针指向输入变量表;与循环有关的变量(L)是指对变量赋值的过程中,或者赋值过程出现在循环体中,或者赋值表达式有与循环有关的成分,此时令变量状态为L;填写变量信息表中的变量联合体(其结点结构见前文介绍):对于+,-,*及括号填写在操作符结构中;填写系数项,默认值为1,若多元函数乘积项有系数,那么填写系数,若为常数项在其上填写常数;填写表中的联合体内容,这一部分是变量信息表的主要内容,它包含的信息是组成该中间变量值的输入变量信息,某个对象的成员变量信息,成员函数信息,中间变量信息,填写不同的指针值,分别指向输入变量表,函数信息表和其它的变量信息表,这里需说明的是对于多个为同一变量名的变量信息表,指向哪一个变量信息表由该变量所在的类或属于哪一个对象确定:若同类中有为这一名称的成员变量,那么就指向这一成员变量的变量信息表;若同类中没有这一名称的成员变量,那么就沿着继承关系向上去找,以找到的第一个同名成员函数为准;若在主函数中使用了中间变量,这时分两种情况,一种情况是变量直接使用的情况,这时要使用主函数中定义的变量或全局变量,指向这些变量的变量信息表或输入变量表即可,另一种情况是在给类中函数发消息时引起的间接变量使用,这时也是要使用主函数中定义的变量或全局变量,指向这些变量的变量信息表或输入变量表即可;同一变量名的输入变量只能有一个输入变量表,当还没确定是输入变量时可当作中间变量处理,可能会出现多个中间变量的变量信息表都指向同一个输入变量的输入变量表的情况,但是只要程序是正确的,就不会产生冲突错误;由于在SOOL程序中规定所有函数声明和实现都只能在类中进行,在给类中函数发消息的时候必有标明是给哪一个对象中的成员函数发消息,而在不同对象中同一名称的成员函数只的一个,因此不会出现歧义;把下一结点指针暂时置为NULL,当有下一个中间变量出现时,指向下一个中间变量的变量信息表结点,同时把上一个变量信息表中的下一结点指针指向该变量信息表.
4.3.4 创建及使用函数信息表
函数信息表不仅影响中间变量和其它函数的值,而且是函数嵌套展开的依据,而函数嵌套展开是本文中的难点,函数信息表建造的好坏与否对函数嵌套能否正确展开影响很大,因此建造函数信息表时应尽量全地记录函数相关信息.
在SOOL语法树中函数声明和实现处创建函数信息表,填写函数信息表结点结构各项值:填写成员函数名;填写函数状态值,函数状态共有四种:Unknown,Known,Input,Loop,它们表示函数为未知函数值函数(U),已知函数值函数(K),函数值组成全部为输入变量(及函数)或已知变量(及函数)(I)和与循环有关的函数(L).这里的处理与前文中变量的处理相类似,值得一提的是与循环有关的函数是指函数实现的时候函数中有循环体或函数的实现在某一个循环体中或函数中包含L型的变量或函数;填写参数表指针,它指向变量信息表,若函数没有参数指针指向空NULL,若函数有多个参数,指针指向的是变量信息表链;填写函数值表指针,初值置为NULL,在有函数嵌套的时候它指向函数展开栈,也可能指向变量信息表;填写类信息表指针,指向函数所属对象的对象生存期表,这主要是用来在需要的时候进行父类查找;把下一结点指针暂时置为NULL,当有下一个成员函数出现时,指向下一个成员函数的函数信息表结点,同时把上一个函数信息表中的下一结点指针指向该函数信息表.
4.3.5 创建及使用输入变量表
在SOOL语法树上输入函数处创建输入变量表,输入函数的参数表中的参数即是输入变量表中的输入变量,输入变量表相对简单但是最后的生成测试用例的进候都是围绕输入变量表进行的.由于在变量声明的时候已经建立了变量信息表,所以在填写输入变量表时可以从变量信息表中拷贝两表中相同的顶,填写输入变量名;填写引用状态位,初值为0,表示在生成测试用例的时候路径上前面的条件表达式没有出现这一输入变量,因而没有给这一输入变量生成一个值,若条件表达式出现这一输入变量,而给这一输入变量赋一个值,那么要把引用状态位改为1;填写变量类型;填写输入变量初值,置为0;把下一结点指针暂时置为NULL,当有下一个输入变量出现时,指向下一个输入变量的输入变量表结点,同时把上一个输入变量表中的下一结点指针指向该输入变量表.
4.4 运行过程中程序中各种信息的存储,查找与处理
SOOL程序测试用例生成器在运行过程中要对SOOL语法树进行遍历操作,查找所有的条件判断表达式存储在路径二叉树上,由于利用ACCENT工具已经在语法树上建立了类信息表,对象生存期表,变量信息表,函数信息表和输入变量表等基本数据结构,这时要利用这些基本的数据结构对路径二叉树上的条件判断表达式进行计算,化简,削去那些不会产生分支的条件表达式,形成新的路径二叉树,然后根据化简后的路径二叉树生成测试用例.
4.4.1 常量的存储,查找与处理
对路径上条件表达式影响最大的是常量,它对表达式的影响主要体现在四个方面,一是某些表达式中的变量的值全部由常量组成,这样经过计算后得到表达式的值,这个条件表达式不会产生分支;二是某些变量的值的一部分为常数项,只需化简常数项;三是某些变量带有系数,这时要化简需判断同类项,而且这些系数影响条件表达式梯度;四是某些变量为高次幂,在求取条件表达式梯度及等式生成测试用例的时候都会对结果产生影响.
对于前三种情况,常量存储在变量信息表中,对于第四种情况,变量的指数存储在路径二叉树中的条件表达式结构中,在生成梯度表达式的时候利用前面这些值得到结果,把前三种情况存在系数或常量位中,把梯度中变量的指数存储在指数位中.
4.4.2 变量的存储,查找与处理
变量要区分中间变量与输入变量,每当程序中有变量声明的时候,就产生中间变量,中间变量填在变量信息表中,每当新产生一个中间变量,就在变量信息表中填加一项;输入变量开始时也作为中间变量填在变量信息表中,当在输入函数中确定输入变量时,把变量信息表中的相应指针指向输入变量表,同时填写输入变量表,在输入变量表中增加一项.
在对程序进行信息流分析的时候,中间变量的值发生改变,修改变量信息表的内容记录这些改变,中间变量值表示成一个链表的形式,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成.显然,在进行化简之前,随着对程序信息流分析的深入,这一链表会越来越长.
在路径二叉树中进行条件表达式计算和化简的时候,由前文介绍的条件表达式结点结构可知,条件表达式是一条由算术运算符,括号,关系运算符以及指向变量信息表的指针,指向函数信息表的指针,指向输入变量表的指针和变量的指数组成的符号链.
路径二叉树上的条件表达式经过计算,化简和削减后,所有的条件表达式中都不再含有括号,指向函数信息表的指针,而只包含算术运算符,关系运算符及指向变量信息表的指针,指向输入变量表的指针和输入变量指数.
4.4.3 函数的存储,查找与处理
函数信息存储在函数信息表中,函数若有嵌套需得使用函数展开栈.
在对程序进行信息流分析的时候,函数的值发生改变,修改函数信息表的内容记录这些改变,函数值表示成一个链表的形式,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成.显然,同中间变量的变量信息表一样,在进行化简之前,随着对程序信息流分析的深入,这一链表会越来越长.
对嵌套函数的展开本文后面有详细介绍.路径二叉树上条件表达式经过计算,化简后,所有指向函数信息表的指针均被消掉,函数不会对化简后的条件表达式产生影响.
4.5 赋值语句及发消息语句的处理
为了生成测试用例,我们考虑的主要方面是赋值语句和发消息语句对条件表达式的影响,因此在这里发消息语句可以看作是多个赋值语句,类似地,函数返回值也可以看作是对函数的赋值语句.
赋值语句的一般形式把一个表达式赋给一个中间变量,该表达式为一个链表,这一链表由算术运算符,括号以及指向变量信息表的指针,指向函数信息表的指针和指向输入变量表的指针组成,赋值的时候把这一个链表赋给这个变量,实现的时候只需修改该中间变量的变量信息表中的指针即可;同时要修改变量信息表的状态位,若表达式中所有变量信息表和函数信息表的状态位均为K,则把该中间变量的状态位置为K;若表达式中有一个变量信息表或函数信息表的状态位为L,则把该中间变量的状态位置为L;若表达式中所有变量信息表和函数信息表的状态位或者为K或者为I(可以没有K,但不能没有I),则把该中间变量的变量信息表的状态位置为I.
4.6 分支语句的处理及路径二叉树的建立
4.6.1 程序块中出现的IF语句的处理
这里所说的程序块中出现的IF语句,是指区别后面的非函数体中的程序块.IF语句是产生程序执行路径分支的原因,由前文的叙述可知并不是每一个IF都会产生分支,并且由于IF语句相互影响,我们在开始建立路径二叉树的时候并不确定哪些IF语句产生分支,我们的做法是对在程序块中出现的IF语句均先假定其产生分支,把IF语句中BOOL表达式作为路径二叉树上的条件表达式,假定表达式成立和表达式不成立产生两条分支,分别沿两条分支填写分支路径上的条件表达式.
由于这样形成的条件表达式不一定产生分支,所以在对表达式计算和化
文章来源于领测软件测试网 https://www.ltesting.net/
