A type system and analysis for the automatic extra

ATypeSystemandAnalysisfortheAutomaticExtractionandEnforcementofDesignInformationPatrickLamMartinRinardLaboratoryforComputerScienceMassachusettsInstituteofTechnologyCambridge,MA02139{plam,rinard}@lcs.mit.eduAbstract.Wepresentanewtypesystemandassociatedtypechecker,analysis,andmodelextractionalgorithmsforautomaticallyextractingmodelsthatcaptureaspectsofaprogram’sdesign.Ourtypesystemenablesthedevelopertoplaceatokenoneachobject;thistokenservesastheobject’srepresentativeduringtheanalysisandmodelextraction.Thepolymorphisminourtypesystemenablestheuseofgeneral-purposeclasseswhoseinstancesmayservedifferentpurposesinthecomputation;programmersmayalsohidethedetailsofinternaldatastructuresbyplacingthesametokenonalloftheobjectsinthesedatastructures.Ourcombinedtypesystemandanalysisprovidethemodelextractionalgorithmswithsoundheapaliasinginformation.Ouralgorithmscanthereforeextractbothstructuralmodelsthatcharacterizeobjectrefer-encingrelationshipsandbehavioralmodelsthatcaptureindirectinterac-tionsmediatedbyobjectsintheheap.Previousapproaches,incontrast,limitedbyanabsenceofaliasinginformation,havefocusedoncontrol-flowinteractionsthattakeplaceatprocedurecallboundaries.Wehaveimplementedourtypechecker,analysis,andmodelextractionalgorithmsandusedthemtoautomaticallyextractdesignmodels.Ourexperienceindicatesthatitisstraightforwardtoproducethetokenannotationsandthattheextractedmodelsprovideusefulinsightintothestructureandbehavioroftheprogram.1IntroductionDesignabstractionssuchasobjectmodels[12]andmoduledependencydiagramsareacentralfeatureofmanysoftwaredevelopmentprocesses.Inthiscapacitytheyprovideawaytoquicklyandeasilyexploredesignalternativesandgivethemembersofthedesignteamacommonandeffectivelanguageforcommunicatingimportantaspectsofthedesign.?ThisresearchwassupportedinpartbyafellowshipfromCanada’sNaturalSciencesandEngineeringResearchCouncil,DARPA/AFRLContractF33615-00-C-1692,NSFGrantCCR-0086154,NSFGrantCCR-0073513,NSFGrantCCR-0209075,anEclipseInnovationGrant,andtheSingapore-MITAlliance.2Inprinciple,thedesignabstractionsshouldremainaprimarysourceofin-formationabouttheprogramforitsentirelifetime.Butthestandardpracticeisforprogrammerstomanuallyimplementthedesignonceithasbeenfinalized,raisingthepossibilityoftheimplementationdivergingfromthedesign.Thisdi-vergencebecomesevermorelikelyoverthelifetimeoftheprogram,limitingthecredibilityoftheoriginaldesignandthereforeitsutilityasasourceofinforma-tionabouttheprogram.Inmostcases,thedesigniseventuallydiscardedandthecodebecomestheprimarysourceofinformationabouttheprogram.Thispaperpresentsanewtypesystemandanassociatedanalysisthatto-gethersupporttheautomaticextractionofdesign-levelinformationfromthesourcecode.Thegoalistoestablishaguaranteedconnectionbetweenthepro-gramanditsdesign,restorethecredibilityofthedesignasareliablesourceofinformationabouttheprogram,andenabledeveloperstousedesignabstractionseffectivelythroughouttheentirelifetimeoftheprogram.Wefocusonabstractionsthatinvolvethestructureoftheheapandtheinfor-mationflow(orlackofsuchflow)betweendifferentsubsystems.Oneparticularlynovelaspectofourtechniqueisthatitaccuratelycapturesevenindirectinter-actionsmediatedbyobjectsintheheap.Existingapproaches,incontrast,focusonlyonthedirectinteractionsthattakeplaceatprocedureormethodcalls.Thekeyideabehindourapproachistoallowthedevelopertousethetypesystemtoplaceatoken(chosenfromafinitesetoftokensfixedatprogramanalysistime)oneachobjectintheprogram;thistokenservesastheobject’srepresentativeduringtheanalysisthatextractsthedesigninformationfromtheprogram.Thisapproachaddressesseveralcommonproblemsthatcomplicatetheeffectiveautomaticextractionofdesigninformation:–MultipleDesignElements,SingleCodeElement:Well-structuredpro-gramsfactorcommonbehaviorandstructureintoasingle,general-purposecodeelement(forexample,acontainerclassorobjectfactory).Differentinstantiationsofsuchanelementoftenhavedistinctconceptualpurposesinthecomputationandshouldthereforecorrespondtodifferentelementsinthedesign.Butstandardanalysisapproachestreateachcodeelementasaunit,conflatingtheattributesofitsdifferentinstantiationsandfailingtocaptureimportantdesign-leveldistinctions.Thepolymorphisminourtypesystemeliminatesthisproblem.Itallowsthedevelopertoplacedifferenttokensondifferentinstantiationsofthesameclasssothattheanalysisseparatesobjectswithdifferentconceptualpurposeseveniftheobjectshappentobeinstancesofthesamegeneral-purposeclass.–SingleDesignElement,MultipleCodeElements:Becausethedesigncapturesaspectsofthecomputationatahigherlevelofabstractionthanthecode,multiplecodeelementsareoftenrequiredtoimplementasingledesignelement.Forexample,aprimaryobjectmaymaintaincomplexinternaldatastructuresthatthedesignabstractsasconceptuallypartoftheobject.Anyapproachthatfailstoabstracttheseinternaldatastructureswilldeliveranoverlydetailedmodelthatobscureskeyaspectsofthedesign.3Ourtypesystemaddressesthisproblembyallowingthedevelopertoplacethesametokenonboththeprimaryobjectandalloftheobjectsthatim-plementitsinternaldatastructures.Theanalysisthentreatstheentirecol-lectionofobjectsasau