（计算机软件与理论专业论文）泛型程序重构技术研究.pdf

摘要 泛型程序设计是一种重要的程序设计风范，它强调使用概念进行程序设计，追求抽象和效率的和谐统 一，以易扩展、易交互的方式表达算法、数据结构及其它软件概念的抽象表示和系统组织，在业界得到了 越来越广泛的关注和应用。 将非泛型风范的遗产软件重构为泛型软件，有利于提高软件的复用性、类型安全性；对泛型软件做进 一步重构，支持其演化，可以改善代码结构，提高软件质量。本文对泛型程序重构模型、非泛型程序实例 重构、泛化关系重构、面向概念的重构等泛型程序重构的关键问题进行了深入研究。 论文的主要研究成果包括： ( 1 ) 为了解决重构正确性分析问题，提出了一个泛型程序重构模型，并分析了常见重构的目的、步 骤和实施效果。在这个模型下，重构可以分为三个部分：前置条件、程序变换和后置条件。使用前置条件 和后置条件来表达重构的保行为性质，可以基于这个模型分析重构前后程序行为的一致性。我们给出了若 干常见的泛型程序原子重构的分析函数，用于表示软件重构的前置条件和后置条件，分析探讨了重构的语 义。此外，我们对常见的泛型程序重构进行了分类总结，从重构的复杂性角度将常见重构分成三类：基本 重构、面向概念的重构和设计模式的重构。 ( 2 ) 针对现有泛型实例重构方法效率不高的问题，提出了一种基于泛型变量类型传播分析的重构方 法。在高效的变量类型传播分析方法基础上，通过改进类型传播图的构造，实现了高效地重构。解决了在 类型传播图上表示类型参数的类型传播问题，使用拷贝节点方式实现了泛型变量属性敏感的分析，精度比 基于属性的传统变量类型传播分析更高。研究了j a v a 程序泛型实例重构中的别名问题。别名可能造成类型 传播分析中的隐式路径，降低分析的精度。探讨了一种基于约束合并的别名分析方法，通过消除别名，提 高了重构的精度。 ( 3 ) 提出了一种基于类型约束分析的泛型类重构方法，解决了现有方法不考虑参数化类型的类型约 束，会在重构中引发类型错误的问题。研究了如何将面向对象软件重构中的泛化关系重构，如提炼接口、 提炼父类( 子类) 、成员移动等，应用于泛型软件，支持泛型软件的演化。我们深入研究了泛型程序的类 型约束规则，提出了一种基于类型约束的泛化关系重构方法，可以保证重构后程序的类型正确性。 ( 4 ) 提出了一种基于源代码使用约束分析的面向概念的c + + 程序重构方法。概念是新的c + + 标准 c + + o x 中出现的语言新特性，从遗产软件中抽取概念，并将遗产软件重构为符合c h 佩标准的代码，对软 件的优化、维护都具有重要意义。在深入研究概念的定义和表示基础上，探讨了如何从遗产软件中提取有 效表达式和关联类型约束，作为构成概念的组成部分，从而发掘出遗产软件中的概念，并实施重构。与现 有方法相比，我们的方法通用性更高，不仅适用于函数模板，也适用于类模板，此外，考虑了由于继承、 函数调用、别名等因素造成的约束，以及关联类型约束，提高了约束分析的精度，结果更接近于c + 斗o x 标准的代码。 关键词：泛型程序设计、软件重构、概念、类型分析、类型约束、别名分析、指向分析 a b s t r a c t g e n e r i cp r o g r a m m i n gi sa l l i n c r e a s i n g l yp o p u l a ra n di m p o r t a n tp r o g r a m m i n gp a r a d i g mf o r s o r w a r e d e v e l o p m e n t i tu s e sc o n c e p tt oe x p r e s st h ef o r m a l i z a t i o no fa na b s t r a c t i o na sas e to fr e q u i r e m e n t so nat y p e t h e g o a lo fg e n e r i cp r o g r a m m i n gi st oe x p r e s sa l g o r i t h m sa n dd a t as t r u c t u r e si nab r o a d l ya d a p t a b l e ，i n t e r o p e r a b l e f o r mv i ac o n c e p t s 。 o no n eh a n d , t h er e u s a b i l i t ya n dt y p es a f e t yo fn o n - g e n e r i cl e g a c ys o f t w a r em a yb eh i g h e ri ft h e ya 托 r e f a c t o r e dt og e n e r i co n e s ；o nt h eo t h e rh a n d , r e f a c t o r i n g sf o rg e n e r i cp r o g r a m sc a ni m p r o v et h eq u a l i t yo ft h e m , a n dm a k et h e me v o l v eb 酣t e ra n db e t t e r t h i sp a p e rf o c u so ns o m ek e yi s s u e so ft h ef o l l o w i n gt o p i c s ：r e f a c t o r i n g m o d e lo fg e n e r i cp m g r a m s ，g e n e r i ci n s t a n t i a t i o nr e f a c t o r i n g , g e n e r a l i z a t i o nf o rg e n e r i cp r o g r a m sa n dc o n c e p t o r i e n t e dr e f a c t o r i n g s t h em a i nc o n t r i b u t i o n so f t h i sp a p e ra r el i s t 酞la sf o l l o w s ( 1 ) p r o p o s i n gam o d e lo fg e n e r i cp r o g r a mr e f a c t o r i n gt oa n a l y s i sb e h a v i o r - p r e s e r v a t i o no fr e f a c t o r i n g s ，a n d a n a l y z e ss o m ec 幻m m o nr e f a c t o r i n g s o b j e c t i v e ，m a i ns t e p sa n de f f e c t b a s e do nt h i sm o d e l ，r e f a c t o r i n g 锄b e c l a s s i f i e di n t ot h r e ep a r t s ：p r e - c x 3 n d i t i o n , p r o g r a mt r a n s f o r m a t i o na n dp o s t - c o n d i t i o n p r e - c o n d i t i o n sa n d p o s t - c o n d i t i o u sa r eu s e dt oa n a l y z eb e h a v i o r - p r e s e r v a t i o np r o p e r t y a n a l y z ef u n c f i o ma l eg i v e nt or e p r e s e n t p r e - c o n d i t i o ma n dp o s t - c o n d i t i o n s c o m m o ng e n e t i cp r o g r a mr e f a c t o r i n g sa r ec l a s s i f i e dt ot h r e ec a t e g o r i e s ：b a s e r e f a c t o r i n g 。c o n c e p to r i e n t e dr e f a c t o r i n g sa n dd e s i g np a t t e r no r i e n t e dr e f a c t o r i n g s ( 2 ) p r o p o s i n gag e n e r i cv a r i a b l et y p ep r o p a g a t i o na n a l y s i st oi m p r o v et h ee f f i c i e n t n e s so fg e n e r i c i n s t a n t i a t i o nr e f a c t o r i n g b a s e do nt h et r a d i t i o n a lv a r i a b l ep r o p a g a t i o na n a l y s i sm e t h o d , t h i sp a p e rp r o p o s e sa g e n e r i ct y p ep r o p a g a t i o ng r a p ht od ot y p ep r o p a g a t i o na n a l y s i s n e w c o n s 廿u c t sa r ea d d e dt ot h eg r a p ht oe x p r e s s g e n e r i ct y p e sa n dv a r i a b l e s ，s ot h eg r a p hi ss u i t a b l ef o rg e n e r i cv a r i a b l ef i e l ds e n s i t i v et y p ea n a l y s i s t h i sp a p e r a l s oa n a l y z e st h ea l i a sp r o b l e mi ni n s t a n t i a t i o nr e f a c t o r i n g , u s i n ga nu n i f i c a t i o nb a s e da l g o r i t h mt oe l i m i n a t e a l i a s e st oi m p r o v er e f a c t o r i n gp r e c i s i o n ( 3 ) p r o p o s i n gat y p ec o n s t r a i n tb a s e dg e n e r a l i z a t i o nr e f a c t o r i n gm e t h o df o rg e n e r i cc l a s s e s t h ec u r r e n t a p p r o a c h e sf o rg e n e r a l i z a t i o nr e f a c t o r i n gd on o ts o l v et y p ec o n s t r a i n t so fp a r a m e t e r i z e dt y p e s ，s ot y p ee f l o r sm a y b ei n t r o d u c e dw h e na p p l y i n gt h e s er e f a c t o r i n g st og e n e r i c p r o g r a m s t h i sp a p e rs t u d i e sh o wt oa p p l y g e n e r a l i z a t i o nr e f a c t o r i n g s ，i n c l u d i n ge x t r a c ti n t e r f a c e ，e x t r a c ts u p e r - c l a s s ，p u l lu pm e m b e r s ，t og e n e r i c p r o g r a m s s o m et y p ec o n s t r a i n tr u l e sf o rt h e s er e f a c t o r i n g sa r ep r o p o s e dt op r e s e r v et y p ec o r r e c t n e s s a c c o r d i n g t ot y p ec o n s t r a i n t sg e n e r a t e db yt h er u l e sat y p ec o n s t r a i n tg r a p hi sc o n s t r u c t e d , a n da l l o w a b l er e f a c t o r e de l e m e n t s c a l lb ed e t e c t e de f f i c i e n t l yb yt r a v e r s i n gt h eg r a p h , a n dr e f a c t o r i n g sf o rg e n e r i cc l a s s e sc a nb ea p p l i e db y t r a n s f o r m a t i o n so f t h eg r a p h ( 4 ) p r o p o s i n gac o n c e p to r i e n t e dr e f a c t o r i n ga p p r o a c hf o rc + + t e m p l a t ep m g r a m sb a s e do ns t a t i cs o u i c o d ea n a l y s i s c o n c e p tw i l lb ean e wl a n g u a g ec o m t m c t i o ni nc 卜o ) 【，w h i c hp r o v i d e ss o l i db a s ef o rd e v e l o p i n g r e u s a b l ea n de x t e n d a b l eg e n e r i cs o f t w a r e i ti sn e c e s s a r yt oi d e n t i f yc o n c e p t si nl e g a c yc + + p r o g r a m s ，a n d r e f a c t o rt h e mt oc + + o xp r o g r a m s t h i sp a p e ra n a l y z e st h eu s a g e s o f t y p ep a r a m e t e r si nl e g a c yp r o g r a m st oe x u a e t v a l i de x p r e s s i o nc o n s t r a i n t sa n da s s o c i a t et y p ec o n s t r a i n t s c o n c e p t sc a nb ei n f e r r e db yt h e s ec o n s t r a i n t s t h e s t u d i e so nc + + s t a n d a r dt e m p l a t el i b r a r y ( s t l ) t oi d e n t i f yp o t e n t i a lc o n c e p t sc o n v i n c et h a tt h em e t h o di s h e l p f u lt oi d e n t i f yc o n c e p t si nl e g a c yc + + p r o g r a m s k e y w o r d s ：g e n e r i cp r o g r a m m i n g , s o f t w a r er e f a c t o r i n 舀c o n c e p t , t y p ea n a l y s i s ，t y p ec o n s u a i n t , a l i a sa n a l y s i s ， p o i n t st oa n a l y s i s 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：盈垒业日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名龇导师签名： 期：a 咿g 第一章绪论 1 1 选题依据 第一章绪论 随着软件技术的不断发展，软件设计方法和手段越来越丰富，继结构化程序设计和面向对象程序 设计方法之后，泛型程序设计方法也在软件设计中占据了重要的地位。泛型程序设计方法强调“使用 概念1 进行程序设计”( p r o g r a m m i n gw i l hc o n c e p t s ) 【4 丌，追求抽象和效率的和谐统一，以富有弹性、 易扩展、易交互的方式表达算法、数据结构及其它软件概念的抽象表示和系统组织。泛型程序设计方 法的主要作用包括：分离算法和数据结构，并以最少的约束假设实现它们，从而提高它们的扩展性和 交互能力；将具体算法抽象为通用算法且无效率损失；消除类型转换操作，实现类型安全的策略。泛 型程序设计方法为增强软件的可重用性、可扩展性，提高软件开发的生产力提供了极大的支持。 近年来随着c h 、j a v a 、c # 等主流面向对象语言对泛型机制支持的不断加强，泛型程序设计技 术得到了快速发展。一些主流面向对象语言早在八十年代已经以参数化类型的方式支持泛型，如c 忖 的模板、a d a 的类属等。今年来，原先不支持泛型的一些流行语言，如j a v a 、c # 等，也纷纷引入 泛型以弥补其不足。其中，泛型程序设计方法在c + + 社区中的应用最为成功。c + + 较早以模板形式支 持泛型程序设计，如今已经诞生了许多高效、可交互操作、扩充性良好的泛型软件库，如标准模板 库( s t l ) 、b o o s t 等。目前，c + + 标准化委员会正在考虑加强对泛型程序设计的支持，准备在新的c + + 语言标准c + + o x 中提供语言设施：概念( c o n c e p t ) 删，从而真接支持泛型程序设计方法。j a v a 在 引入泛型后，利用泛型机制重写了标准库，提高了类型安全性。可以预计，泛型程序设计方法将给 软件发展带来巨大的机遇。泛型软件的分析、理解和维护，已经成为软件领域的一个重要课题。 应对并处理变化，是软件开发的根本复杂性之一【。随着环境的变化、需求的变更，软件都面 临一个不断的演化过程。正在设计开发的软件，随着对领域知识的不断深入了解，以及对需求变更的 适应，也需要对软件设计及实现做出必要的修改。已经投入使用的遗产软件，可能面临功能扩充等要 求，需要修改、升级。软件从其设计开始，就在不断地演化。 存在大量非泛型风范的遗产软件，其代码是以结构化或者面向对象的方式设计实现的。虽然结 构化和面向对象程序设计方法各有优点，然而也存在一些问题，如类型安全性不高、可重用性不高、 或者是为了提高可重用性而丧失了部分软件效率等。例如在引入泛犁之前，j a v a 容器库的实现是面 向对象风范的，使用o b j e c t 作为容器元素的声明类型，导致在其实现和使用中，充斥了大量的类型 转换和类型测试代码，使用时程序员必须自己负责维护容器内元素的类型，不仅影响程序的效率， 也缺乏类型安全性。 有些泛型风范的软件，随着环境的变化、需求的变更，软件功能的增加和调整使得软件可能偏 离原来的设计，代码变得混乱、纠结。 因此，需要一种手段，一方面将非泛型遗产软件泛型化，即将它们重写为泛型软件，充分利用 泛型程序设计方法的优点，提高软件的可复用性、可扩展性、类型安全性等；另一方面，支持泛型 软件的进一步演化，改善代码结构，提高代码质量。 软件重构是通过变换代码结构，在保证系统行为正确性的前提下，改善原有代码，提高软件质 量的重要技术【7 卅，已经在业界得到了广泛的应用。从本质上说，软件重构就是“在代码写好以后 改进它的设计”h 1 ，通过调整已有代码，重新组织软件结构，处理混乱的继承体系，使软件体系结 构更清晰，使新功能增加更容易，利于充分利用以前的投资，减少重复劳动，使程序更简化更有性 能，提高软件质量，支持软件的设计和演化。可见，软件重构技术可以很好地解决上述问题。 然而，软件重构是一件复杂的程序转换工作。由于重构所涉及的代码往往比较发散，手工重构 容易出错，费时费力，需要自动化的辅助工具。程序分析技术为自动化重构工具设计开发提供了坚 1 概念( c o n c e p t ) 是泛型程序设计领域的一个专有名词以下在没有歧义的情况下，我们不再强调该名词与一般意 义的名词“概念”的区别 1 东南大学博士学位论文 实的技术基础。 本文旨在通过对泛型程序重构相关技术的研究。深入探讨自动化重构模型，以及类型分析、别 名分析等程序静态分析技术，在此基础上研究泛型程序重构方法，提高重构的效率和精度，提高重 构的自动化程度，从而支持泛型软件的设计、演化和维护。对泛型程序重构进行了分类和总结；分 别针对j a v a 和c + + 语言的特点，分别提出了基于类型分析和面向概念的重构方法，一方面研究了如 何将非泛型程序重构为泛型程序，另一方面探讨了已泛型化程序的重构，支持泛型程序的进一步演 化；探讨了泛型软件重构支撑系统的设计和实现，为自动化重构工具的实现奠定了基础。 1 2 国内外研究现状 早期软件重构的研究工作集中于面向对象软件重构1 1 】，主要研究内容包括：总结软件重构方 法，丰富软件重构的手段，研究各类程序分析技术以提高软件重构的精度和效率。最早对重构进行 正式讨论的文献是o p d y k ewf 的博士论文【7 】。o p d y k ewf 利用前置条件给出了重构的形式化定义， 并总结了2 3 种面向对象软件的重构。到九十年代末期，随着泛型程序设计方法在软件设计领域得到 越来越广泛的应用，工业界和学术界开始有越来越多的人开展泛型程序重构的相关技术研究。 程序分析技术是软件重构的基础，可以利用程序分析技术确定待重构代码，分析重构前后程序 语义一致性的变化等。类型分析和指向分析技术是软件重构中最常用的两种技术，它们的精度和效 率往往决定了重构的精度和效率。目前，有关类型分析与指向分析已经有相当多的研究【6 1 d 叭】，人们 主要关注如何在不同应用中权衡它们的精度和效率。 类型分析技术可以获取程序的类型信息，有利于待重构代码的确定及保证重构后程序的类型安 全性。类型分析算法通过对程序的静态分析得到类型信息，这种方法可以看作是一个约束求解的过 程。每个表达式和语句都蕴含了程序中类型结构信息的某些约束。推导算法通过静态分析得到所有 约束，并通过求解约束推导出类型。根据约束的表示形式，现有的类型推导算法可以分为两类：基 于合一的( u n i f i c a t i o n - b a s e d ) 和基于包含的( i n c l u s i o n b a s e d ) 。m i l n e rr 的类型推导是经典的基于 合一的类型推导方法【7 1 】，通过自下而上的遍历抽象语法树，生成程序中每个表达式对应的类型等式， 然后经过合并求解这些等式，从而得到类型信息。这种算法效率高。基于包含的类型推导通常是根 据数据流建立形如t l t 2 的子类型约束，并进行类型求解【6 1 1 。这种方法时间复杂度一般与程序的执 行时间近似，从而保证所有的运行时路径和数据流路径都可被覆盖。后来的学者在这两类经典算法 基础上，为了提高分析的精度和效率，提出了若干改进，如k - c f a 算法 9 7 1 、c p a 算法 6 2 1 、d c p a 算 法等【8 2 1 。 指向分析的目的是分析变量的指向集，从中可以归纳出变量间的别名关系。准确的指向信息和 别名关系能够提高程序重构的精度。人们在指向分析方面做了大量的研究工作，提出了不少分析方 法 s 4 - 9 引。与类型分析方法类似，指向分析方法也可分为基于合一的和基于包含的两类。基于合一的 流不敏感方法复杂度低，能够适用于大规模的程序，但其精度也很低，很难满足人们的需求。基于 包含的方法也可分为流敏感的和流不敏感的两种：流敏感的方法精度较高，但复杂度也很高，只适 用于小规模的程序；流不敏感的方法精度和复杂度介于前两类方法之间，是人们研究的重点。 a n d e r s e nl0 最先提出基于包含的分析方法晔】，他将程序中变量间指向集的包含关系抽象为一 个约束系统，原问题转换为该系统的求解。d a sm 则将包含关系表示成图，将原问题转换为计算图 上的动态传递闭包【s 6 1 ，他的方法被后来的学者推广到上下文敏感的分析。 类型分析和指向分析面临的主要问题是精度与效率的平衡问题，即在不同应用背景中寻找能满 足特定应用需求的方法。目前人们的主要目标一方面致力于提高方法精度，另一方面也在努力研究 适用于大规模程序分析的各类方法。在软件重构研究中，面临同样的问题，即寻找适用于重构的分 析方法，在精度和效率中找到平衡。 目前泛型程序重构技术的研究主要集中在遗产软件的泛型化重构，包括两个方面f 阳i i ：是参 数化重构( p a r a m e t e r i z a t i o n ) ，二是泛型实例重构( i n s t a n t i a t i o n ) 。 参数化重构和泛型实例重构是两个相关重构，目的都在于将非泛型遗产软件重构为泛型软件。 2 第一章绪论 参数化重构通过为已有非泛型类或非泛型函数引入类型形参，将其重构为泛型类或泛型函数。在对 某个非泛型类实施参数化重构为泛型类后，该类的使用者代码可以通过使用泛型实例重构确定实例 化该类的类型实参，并将使用者代码重构为使用泛型类的代码。 参数化重构的主要活动是分析类或函数内各程序元素的使用，从而引入类型形参，常用技术有 类型分析和指向分析等。 d u g g a nd 针对p o l y j a v a 语言提出了一种自动化的参数化重构方法1 3 0 】。p o l y j a v a 是j a v a 语言的 一个子集，包含了一个参数化类型的语言扩充。他们使用类型推导技术为类中的每个声明变量都推 导出一个类型参数。这样做的缺点是会过度泛型化，即推导出冗余的类型参数。 d o n o v a na 等人提出了一种基于指向分析的泛型实例重构方法【2 啦引。他们先用上下文敏感的分 析算法c p a 确定对象分配点的可能类型，然后使用基于集合约束求解的上下文无关分析选择在分配 点和声明点保持一致的类型。其第一阶段的指向分析最坏时间复杂度是指数级的，第二阶段的分析 是一种典型的w o r k l i s t 算法，需要反复迭代，两阶段分析总体时间复杂度较高。 d i n c k l a g edv o n 等人在i l 晰廿l 重构系统中同时考虑了泛型程序参数化重构与实例重构 2 7 1 。他们 的方法也是基于c p a 算法先进行分析，再进一步通过类型约束求解确定待重构代码。其方法可以为 程序员提供有用的参考。 t i pf 等人提出的泛型实例重构方法先用c p a 计算方法的上下文，再将其用于约束的生成与求 解，从而得到重构结果1 3 2 - 3 4 1 。他们的方法能推导出继承自类库类的用户自定义类型的使用。之后他 们对工作进行了改进，同时考虑了参数化和实例重构问题。其方法通过推导程序中各元素的类型约 束确定重构代码。约束求解的过程也使用w o r k l i s t 算法，需要迭代求解。 上述工作都是针对j a v a 语言的开展的泛型化重构研究，也有部分学者针对其他语言展开了探 讨。s i f f m 等使用类型推导分析代码中潜在的函数参数化多态【3 l j ，从而将c 函数重构为c + + 模板函 数。他们主要通过操作符重载、引入构造函数包装常量引用、以及结构化类型匹配等方法识别参数 化多态。他们的方法也会导致过度泛型化，推导出过多不必要的类型参数。 基于类型分析的方法是目前泛型程序重构研究中使用的主要方法，也有部分学者尝试通过其他 途径实现泛型程序的重构。s u r ed e 等研究了如何推导出类型参数化的函数【2 1 1 。他们的方法针对c + + 目标代码，在c + + 模板函数实例化的时候进行推导。他们的推导方法是基于代码相似度比较的，而 不是类型推导方法。s u t t o na 等人提出了一种面向概念的c 抖函数重构方法，其方法主要是通过分 析源代码的使用约束，将c 卜十函数重构为符合新的c + + 标准c + + o ) 【的代码例。 有些学者对编译时参数化类型推导进行了研究【柏4 l l ，目的是减轻使用语言的参数化类型机制支 持显式参数化的负担。这些研究主要用于函数式语言，且重点关注为函数引入类型参数，并不考虑 类或模块的类型参数化。 国内对软件重构相关工作的研究开展得不多，且主要集中于面向对象软件重构技术研究。上海 大学的缪淮扣等按照代码味道的特征进行分类【4 2 】，对类之间结构型代码味道的自动化检测原理进行 了研究。上海交通大学张申生等研究了基于本体映射规则的软件集成重构【4 3 】，他们分析了软件代理 与其本体间的关系，给出了遗产软件重构框架，并提出了基于本体转换的异构系统语义互操作算法。 南京大学的周毓明、周天琳等研究了基于度量的重构方法，他们利用模块内聚性从结构化程序中抽 取对象【4 5 1 ，此外，对大规模c + + 软件的依赖性进行了分析，提出了一种基于包依赖性度量的重构方 法 2 4 - 2 6 。 也有部分国内学者对软件重构的相关应用进行了研究，如黄卫平研究了重构预处理在提高软件 模型检测效率中的应用，尝试利用重构将大型程序分解成语义致的小型过程，通过这种预处理 避免模型检测中状态空间的重复搜索。 1 3 存在的问题分析 尽管目前人们在泛型程序重构相关技术研究方面做了很多工作，取得了很多成果，然而，仍有 一些问题亟待解决。主要包括： 3 东南大学博士学位论文 ( 1 ) 泛型程序设计方法自s t l 出现后为人们广泛关注，近年来飞速发展，得到了业界非常广泛 的认可和使用。然而。目前人们使用的重构方法主要是针对结构化或面向对象软件的，尚未有学者 对泛型程序重构方法做较为全面的分析总结。全面良好的重构目录，有助于推广重构方法的使用， 也有利于程序员认识和接受重构，从而为泛型程序设计提供有力的支持。 ( 2 ) j a v a 泛型程序的重构方法主要是基于指向分析和类型推导的，现有方法时间复杂度较高。 重构是伴随敏捷软件开发为程序员广泛接受的一个重要行为，即时交互、快速反馈是其主要特征， 因此，时间复杂度低的自动化重构方法更易为程序员接受。如何在保证重构精度的前提下，提高重 构的效率，是我们考虑的一个重点。 ( 3 ) 目前有关泛型程序重构的方法关注的都是泛型化重构，即考虑如何将非泛型的遗产软件重构 为泛型软件，尚未有学者考虑将现有的常见重构手段应用到已泛型化软件中。改善泛型软件的内部 结构，支持泛型软件的进一步演化，也是非常值得研究的问题。 ( 4 ) 泛型程序设计方法的核心在于使用概念，重构应该充分考虑概念的作用。现有重构方法多从 类型分析的角度出发，研究如何将参数化类型引入程序，不考虑概念在程序中的作用，不能充分利 用泛型的优点。概念在新的c + + 语言标准c h 锨中将成为一个新的语言设施，这将极大地推动泛型 程序设计方法的发展。如何在重构中考虑概念的影响，将遗产代码重构为使用概念的代码，是一个 重要的问题。 1 4 主要研究内容及创新点 根据上述讨论和国内外关于泛型程序重构技术的研究现状，本文在以下几个方面展开深入研究： ( 1 ) 泛型程序重构模型研究 在前人工作基础上，提出了一个泛型程序重构模型。在这个模型下，重构可以分为三个部分： 前置条件、程序变换和后置条件。使用前置条件和后置条件来表达重构的保行为性质，可以基于这 个模型分析重构前后程序行为的一致性。 使用分析函数表示软件重构的前置条件和后置条件，给出了若干常见的泛型程序重构的分析函 数，分析探讨了重构的语义。将原子重构进行组合，可以构成其他复合重构。 此外，我们对常见的泛型程序重构手段进行了分类总结，从重构的复杂性角度将常见重构分成 了三类：基本重构、基于概念的重构和设计模式的重构。给出的重构目录列举了这些常见重构，并 在上述重构模型基础上，利用分析函数分析了它们的目的、步骤和实施效果。 j a v a 程序泛型实例重构技术研究 针对现有泛型实例重构方法效率不高的问题，提出了一种基于泛型变量类型传播分析的重构方 法。变量类型传播分析是一种高效的类型分析方法，然而，由于未考虑参数化类型的传播问题，其 不适用于泛型实例重构。此外，传统的变量类犁传播分析是一种基于属性的分析( f i e l db a s e d ) ，精 度不高。如何对其进行扩充，从而高效的得到泛型实例所用的类型实参，是我们研究的重点。 为了保证重构的精度，我们还研究了j a v a 程序泛型实例重构中的别名问题。别名可能造成类型 传播分析中的隐式路径，降低分析的精度。我们探讨了一种基于约束合并的别名分析方法，通过消 除别名，提高了重构的精度。 ( 3 ) 泛型类重构技术研究 针对目前泛型程序重构研究仅关注泛型化重构的问题，我们研究了如何将面向对象软件重构中 常见的手法应用于已泛型化软件，支持泛型软件的演化，重点探讨了泛化关系重构的实施。 泛化关系重构包括提炼接口、提炼父类( 子类) 、成员移动等，是面向对象软件重构中极为常见 的一类重构。将现有面向对象软件的泛化关系重构方法应用到泛型软件，由于它们来考虑参数化类 型约束，会产生类型错误。我们深入研究了泛型程序中的类型约束规则，提出了一种基于类型约束 的泛化关系重构方法，可以保证重构后程序的类型正确性。 4 第一章绪论 面向概念的a 斗程序重构技术研究 概念是c h 戗标准草案中出现的语言新特性，将遗产软件重构为符合c h 锨标准的代码以使 用概念，对软件的优化、维护都具有重要意义。我们在深入研究概念的定义和表示基础上，探讨了 如何从遗产软件中提取有效表达式和关联类型约束，作为构成概念的重要部分，从而发掘出遗产软 件中的概念，进一步实施重构。 泛型程序重构支撑系统研究 典型的重构工具一般都集成到某种开发工具中，便于程序员使用，因此，我们以f _ , e l i p s e 为基础， 研究了如何构建一个泛型程序重构的支撑系统。主要探讨了如何有效地支持泛型软件各类信息的表 示，实现泛型软件重构中信息一致性的维护，如何集成多种程序分析技术，更好地实现自动化重构 功能。 论文的主要成果和创新点如下： - 提出了一个泛型程序重构模型，对常见泛型程序重构方法进行了分类总结，给出了常见泛型 程序重构目录，并使用分析函数给出了重构的前置条件和后置条件，分析了它们的实施步骤 和效果； - 针对现有方法效率较低，不能满足即时、快速反馈的重构需求，提出了一种基于改进的变量 类型传播分析的j a v a 程序泛型实例重构方法，并通过解决重构中的别名问题，提高了分析 的精度，且保持高效率； - 提出了一种基于类型约束的j a v a 泛型程序泛化关系重构方法，解决了现有泛化关系重构方 法仅关注非泛型软件，重构泛型软件时会引入类型错误的问题； - 提出了一种基于源代码静态分析的c h 戗泛型程序重构方法，通过抽取源代码中的有效表 达式约束和关联类型约束，识别代码中潜在的概念，将c + 斗9 8 标准的模板程序重构为符合 a 斗o ) 【标准的程序，与现有方法相比，识别概念的准确度更高； - 提出了泛型软件重构支撑框架的设计，支持多种语言程序的不同重构。虽然重构是语言相关 的行为，使用一个统一的框架，设计有效的程序中间表示，有利于将同一种重构方法用于多 种不同语言程序，并维护重构中各类软件实体之间的一致性，降低实现成本。 1 5 论文结构 论文全文共七章，主体内容包括五个部分：( 1 ) 第二章研究了泛型程序重构模型，对常见的泛型 程序重构进行了分类总结；( 2 ) 第三章从类型分析的角度，研究了j a v a 程序泛型实例重构问题；( 3 ) 第 四章提出了面向重构的泛型程序类型约束规则，基于这些规则探讨了泛化关系重构中如何保持程序 的类型正确性；( 4 ) 第五章研究了面向概念的重构方法，以c h 语言为例，探讨了如何将遗产软件重 构为符合c h 呶标准的代码：( 5 ) 第六章对泛型软件重构支撑系统的设计与实现进行了分析和探讨。 各章节内容组织如下： 第一章作为论文的绪论，介绍了泛型程序重构技术研究的背景、研究目的和意义；介绍了国内 外现有的研究现状和仍存在的不足；描述论文的研究方案，在给出研究内容和方法后，简要地介绍 研究论文的创新点和论文结构。 第二章介绍了一些基本知识和概念；给出了一个泛型程序重构模型，提出了一系列泛型程序的 重构分析函数，并使用这些分析函数分析了常见的若干重构的前置条件和后置条件，讨论了它们的 实施步骤和效果。 第三章提出了一种基于改进的变量类型传播分析的j a v a 程序泛型实例重构方法。通过改进传统 的变量类型传播分析，构造了泛型程序的类型传播图，提出了一种泛型变量属性敏感的类型传播分 析方法，并讨论了传播分析中的别名问题。可以在比较低的时间复杂度下完成重构，并取得满意的 效果。 第四章提出了一种基于类型约束的j a v a 泛型程序泛化关系重构方法。深入研究了泛化关系重 5 东南大学博士学位论文 构，提出了一组针对j a v a 泛型程序重构的类型约束规则，并分析了如何使用这组规则实施提炼接口、 提炼父类、成员移动等重构，解决了使用现有方法会破坏程序的类型正确性的问题。 第五章提出了一种基于概念的c 什泛型程序重构方法。概念是泛型程序设计方法的核心，通过 源代码静态分析，从中提取有效表达式约束和关联类型约束，并基于约束集识别代码中潜在的概念， 从而将遗产代码重构为符合c + 斗o x 标准的代码。 第六章探讨了泛型程序重构支撑系统的设计和实现。主要研究了在e c l i p s e 集成开发环境下，如 何设计和组织程序的各种中间表示，从而利于维持重构前后程序语义的一致性；同时探讨了如何集 成多种程序分析手段，实现一个泛型程序重构支撑系统。 第七章对研究进行了总结和展望，提出了现有工作仍存在的一些问题以及后续的一些可能解决 方案。 6 第二章泛型程序设计基本知识 第二章泛型程序重构模型 本章首先介绍了泛型程序设计方法的一些基础知识和基本概念，分析了程序设计语言中两种不 同泛型设施对泛型程序重构方法的影响；然后给出了一个泛型程序重构模型，以及该模型下的若干 重构分析函数；最后对常见的泛型程序重构进行了分类总结，利用分析函数给出了一些常见重构的 条件，分析了重构的实施步骤和效果。 2 1 泛型程序设计基础知识 泛型程序设计是继结构化和面向对象程序设计方法之后，又一种对软件开发领域造成重要影响的 程序设计风范。泛型程序设计方法强调以概念( c o n c e p t ) 为核心进行程序设计，通过对领域知识的 抽象，形成具有通用性、交互性强的软件组件，使软件具有更高的复用性。参数化类型是支持这一程 序设计风范的基本语言设施。 2 1 1 基于概念的程序设计 泛型程序设计的提出可以追溯到八十年代。1 9 8 7 年m u s s e rdr 和s t e p a n o v a a 等人利用a d a 语言的 类属机制( g e n e r i c s ) 设计了一个a d a 程序库1 5 5 1 ，支持泛型程序设计的某些理念。这是泛型程序设计发 展的早期阶段。在这个阶段，人们利用参数化类型机制支持泛型程序设计的基本理念，例如a d a 的类 属，c _ h 的模板等。使用参数化类型，可以减少重复代码，并设计出具有较高复用性和类型安全的函 数及抽象数据类型。到九十年代末期，j a v a 等面向对象语言出于对类型安全性的需求，也引入了参数 化类型机制，并主要用于容器库的实现1 5 2 , 5 3 j 。 例如，要实现一个求和功能的函数，其中一种实现方式是不使用模板，其针对的是特定类型( 整 型数组) 元素的求和，如图2 1 ( a ) 所示。另一种实现方式则是使用参数化类型的求和函数，如图2 1 ( b ) 。 使用参数化类型的好处是“去类型化”，使得该函数与类型无关，不仅适用于某特定类型，还适用于 其他多种类型。这样，不仅提高了函数的可复用性，消除了冗余代码，还提高了代码的可维护性。因 为如果不使用参数化类型，对于不同类型的数据就需要不同的重载函数，造成代码冗余，且实现同一 功能的函数代码分散，增加了代码维护的难度。 i n ts u m ( i n t a r r a y , i n tn ) ( i n tr e s u l t = 0 ； f o r ( m t i = o ；i n ；+ + i ) r e s u l t = r 嘲u l t + a r r a y i ； r e t u r nr e s u l t ；