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表達式作為路徑二叉樹上的條件表達式,假定表達式成立和表達式不成立產生兩條分支,分別沿兩條分支填寫分支路徑上的條件表達式.
由于這樣形成的條件表達式不一定產生分支,所以在對表達式計算和化
文章來源于領測軟件測試網 http://www.kjueaiud.com/
