ม਺ʹ֨ೲ͞ΕΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆͨ͠Ծ૝
ϝιου‫ͼݺ‬ग़͠ղܾख๏
An approach for virtual method call resolution with an assumption ofa variable typeࣛౡ ༔∗ ੴඌ ོ† Ҫ্ ࠀ࿠‡͋Β·͠ ੩తղੳʹ͓͍ͯԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾ͸ॏཁͳٕज़Ͱ
͋Γɼ‫ط‬ଘ‫Ͱڀݚ‬͸‫ͼݺ‬ग़͞ΕΔՄೳੑͷ͋Δϝιου͢΂ͯΛ໢ཏͭͭ͠ਫ਼౓ΛߴΊΔख๏͕ఏҊ͞Ε͍ͯΔɽ͔͠͠ϓϩάϥϜཧղͰ͸ɼ։ൃऀ͸ม਺ʹ֨ೲ͞ΕΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆͯ͠ϝιουͷ‫ͼݺ‬ग़ؔ͠܎Λௐࠪ͢Δ͜ͱ͕͋Δɽຊ‫Ͱڀݚ‬͸ɼม਺ʹ֨ೲ͞ΕΔΦϒδΣΫ
τ͕ಛఆͷ‫͋Ͱܕ‬ΔͱԾఆ͞Εͨ৔߹ʹɼͦͷ‫ܕ‬৘ใΛ༻͍ͯɼଞͷม਺ͷΦϒδΣΫτͷ‫͍ͯͭʹܕ‬΋Ұ؏ͨ͠‫ܕ‬৘ใͷಛఆΛߦ͍ɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾΛߦ͏ख๏ΛఏҊ͢Δɽ࣮‫Ͱݧ‬͸ɼ‫ط‬ଘख๏ͱఏ
Ҋख๏ͱͰ࡞੒͞ΕΔίʔϧάϥϑͷൺֱΛߦ͍ɼఏҊख๏ͷ༗ޮੑΛ֬ೝͨ͠ɽ

Summary. In static analysis, virtual method call resolution is an important technique. Several methods are propsed for detecting all callable
methods precisely. In a case of program comprehension, call relations
should be taken on assuming a variable type. This paper proposes a
new approach for resolving dynamic binding; our approach identiﬁesvariables aﬀected by type assumptions and then consistently resolves
dynamic binding. In an experiment, we compared call graphs made byexisting methods and ones made by our approach, then conﬁrmed theeﬀectiveness of our approach.

1

͸͡Ίʹ

Java ʹ୅ද͞ΕΔΦϒδΣΫτࢦ޲ϓϩάϥϛϯά‫Ͱޠݴ‬͸ɼԾ૝ϝιου‫ͼݺ‬ग़͕͠ఏ‫͞ڙ‬Ε͍ͯΔɽԾ૝ϝιου‫ͼݺ‬ग़͠Ͱ͸ɼ࣮ߦ࣌ʹ‫ݺ‬͹ΕΔϝιου͸
੩తʹ͸ܾఆ͞Εͣɼ࣮ߦ࣌ͷϨγʔόΦϒδΣΫτͷΫϥεʹΑΓܾఆ͞ΕΔɽιʔείʔυʹରͯ͠੩తղੳΛߦ͏৔߹͸ɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾɼ͢ͳΘͪɼԾ૝ϝιου‫ͼݺ‬ग़͠ʹΑΓ࣮ߦ࣌ʹ‫ݺ‬͹ΕΔՄೳੑͷ͋Δϝιουͷू߹Λಛఆ͢Δ࡞‫ۀ‬Λߦ͏ඞཁ͕͋ΔɽԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾख๏ͱͯ͠ɼΫϥε֊૚ղੳ [1]ɼRapid Type Analysis [2]ɼVariable Type Analysis [3]ʢVTAʣͱ͍ͬͨํ๏͕ఏҊ͞Ε͍ͯΔɽ͜ΕΒͷํ๏͸ɼओͱͯ͠ίϯύΠϥʹΑΔϓϩά
ϥϜͷ࠷దԽΛ໨తͱ͓ͯ͠ΓɼԾ૝ϝιου‫ͼݺ‬ग़͠Ͱ‫ͼݺ‬ग़͞ΕΔՄೳੑ͕͋
ΔϝιουΛ͢΂ͯ໢ཏ͢Δඞཁ͕͋ͬͨɽ
͔͠͠ɼϓϩάϥϜཧղ΍σόοάΛ໨తͱͯ͠੩తղੳΛߦ͏৔߹ɼ։ൃऀ͕
஫໨͍ͯ͠Δม਺ʹಛఆͷ‫ܕ‬ͷΦϒδΣΫτ͕֨ೲ͞Ε͍ͯΔͱԾఆ͍ͨ͠৔߹͕
͋Δɽ ྫ͑͹ɼFluid Source Code Views [4] ΍ Code Bubbles [5] Ͱ͸ϝιου‫ͼݺ‬ग़͠ΛΠϯϥΠϯల։ͨ݁͠ՌΛදࣔ͢Δ͕ɼར༻ऀ͸‫ͼݺ‬ग़͠จ͝ͱʹϨγʔόΦϒδΣΫτͷ‫ܕ‬Λબ୒͠ͳͯ͘ͳΒͳ͍ɽ·ͨɼಉҰΦϒδΣΫτ͕֨ೲ͞ΕΔ
ม਺ʹରͯ͠΋ར༻ऀ͕‫ݸ‬ผʹಉҰͷ‫ܕ‬ΛׂΓ౰͍͔ͯͯͳ͚Ε͹ͳΒͳ͍ɽେᆘ
Β [6] ͷఏҊ͢Δύλʔϯநग़ख๏Ͱ͸ɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷΠϯϥΠϯల։Λߦͳ͍ͬͯΔ͕ɼಉҰͷΦϒδΣΫτΛ࢖༻͢Δෳ਺ͷ‫ͼݺ‬ग़͠จͰҰ؏ͨ͠‫ܕ‬ͷղܾ͕ͳ͞Ε͓ͯΒͣɼ‫ʹ࣮ݱ‬͸‫͜ى‬Γಘͳ͍‫ͼݺ‬ग़͠‫ྻܥ‬Λநग़͢ΔՄೳੑ͕∗Yu Kashima, େࡕେֶ େֶӃ৘ใՊֶ‫ڀݚ‬Պ
Takashi Ishio, େࡕେֶ େֶӃ৘ใՊֶ‫ڀݚ‬Պ‡
Katsuro Inoue, େࡕେֶ େֶӃ৘ใՊֶ‫ڀݚ‬Պ†

FOSE2012

͋Δɽ͜ΕΒͷख๏ʹ͓͍ͯɼ։ൃऀ͕஫໨͍ͯ͠Δม਺ v ͕ಛఆͷ‫ ܕ‬C ͷΦϒδΣΫ
τΛࢀর͍ͯ͠ΔͱԾఆͨ͠ͱ͖ɼv ΛϨγʔόΦϒδΣΫτͱ͢ΔԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾ͸ɼv ͷ‫ܕ‬͸ৗʹ C Ͱ͋Δͱ͍͏ԾఆͷԼͰߦ͏ͷ͕๬·͍͠ɽ·ͨɼv ͷ஋Λ୅ೖ͞ΕΔม਺ͳͲɼ୅ೖ͞ΕΔΦϒδΣΫτͷ‫ ͕ܕ‬v ʹґଘ͢Δม਺͕ϨγʔόΦϒδΣΫτͱͯ͠ར༻͞ΕΔ৔߹ʹ͍ͭͯ΋ಉ༷ʹѻ͏͜ͱ͕๬·͍͠ɽ͞Βʹɼ‫ܕ‬ΛԾఆ͢Δ͜ͱͰ‫ͼݺ‬ग़ؔ͠܎͕ͳ͘ͳΔϝιουʹ͍ͭͯ͸ɼҾ਺΍໭Γ஋ͷӨ‫ڹ‬Λআ‫͢ڈ‬Δ͜ͱ΋ॏཁͰ͋Δɽ‫ݱ‬ঢ়ɼ্‫ه‬ͷΑ͏ʹม਺ʹಛఆͷ‫ܕ‬ͷΦϒδΣΫτ͕୅ೖ͞Ε͍ͯΔԾఆͷԼͰɼϓϩάϥϜશମͷԾ૝ϝιου‫ݺ‬ͼग़͠ΛҰ؏ͯ͠ղܾ͢Δख๏͸ఏҊ͞Ε͓ͯΒͣɼ·ͨख࡞‫Ͱۀ‬Ұ؏ͨ͠ղܾΛߦ͏ͷ͸ɼϓϩάϥϜαΠζͷංେԽ΍ม਺Ͳ͏͠ͷෳࡶͳΤΠϦΞεͷ໰୊͔Βࠔ೉Ͱ͋Δͱ༧૝͞ΕΔɽ
ͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼ͋Δม਺ʹ୅ೖ͞Ε͍ͯΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆͨ͠৔߹
ͷɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾํ๏ΛఏҊ͢Δɽຊख๏͸ VTA Ͱ΋༻͍ΒΕͯ
͍Δ Type Propagation GraphʢTPGʣΛར༻͠ɼԾఆͨ͠‫ʹܕ‬ґଘ͢Δม਺Λಛఆ͠ɼͦΕΒͷม਺Λ༻͍ͨԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾΛߦ͏ɽ͞Βʹɼղܾͷ݁Ռ‫ͼݺ‬ग़͞Εͳ͍͜ͱ͕൑໌ͨ͠ϝιου͕͋Δ৔߹͸ɼTPG ΛՃ޻͠ VTA Λ࠶౓ߦ͏͜ͱʹΑΓɼ‫ݺ‬͹Εͳ͘ͳͬͨϝιουͷӨ‫ڹ‬Λআ‫ͨ͠ڈ‬Ծ૝ϝιου‫ݺ‬ͼग़͠ͷղܾ݁ՌΛಘΔɽఏҊख๏Λ࣮૷͠ɼ࣮‫࣍Ͱݧ‬ͷ 3 ͭͷௐࠪΛߦͬͨɽ·ͣɼෳ਺ͷ‫ܕ‬ͷΦϒδΣΫ
τΛࢀর͠͏Δม਺Λௐࠪͨ͠ɽ࣍ʹɼͦΕΒͷม਺ʹରͯ͠ɼͦͷม਺ͷ‫ʹܕ‬ґଘͯ͠‫·ܾ͕ܕ‬Δม਺͕ϨγʔόΦϒδΣΫτͱͯ͠༻͍ΒΕΔϝιου‫ͼݺ‬ग़͠਺Λௐࠪͨ͠ɽͦͯ͠ɼ‫ط‬ଘख๏ʹΑΔίʔϧάϥϑͱɼ‫ܕ‬ͷԾఆͱ TPG ͷՃ޻ɼͦͯ͠࠶౓ͷ VTA Λߦͬͨ͋ͱͷίʔϧάϥϑΛൺֱͨ͠ɽ࣮‫ݧ‬ͷ݁Ռɼෳ਺ͷ‫ܕ‬ΛऔΓ͏Δม਺ͷׂ߹͸શମʹൺͯ͠গ਺Ͱ͋ͬͨ͜ͱɼͦͷ͏ͪԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾʹӨ‫ڹ‬Λ༩͑ΔΑ͏ͳม਺͸͞Βʹগ਺Ͱ͋ͬͨ͜ͱɼ͔͠͠ɼద
౰ͳม਺Λબ୒͢Δ͜ͱͰίʔϧάϥϑͷαΠζΛେ͖͘‫ݮ‬গͤ͞ΔΑ͏ͳ৔߹͕
͋Δ͜ͱΛ֬ೝͨ͠ɽ
ຊ࿦จͷओͳߩ‫ݙ‬͸ҎԼͷ௨ΓͰ͋Δɽ
• ม਺͕ࢀর͢ΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆͨ͠ঢ়‫Ͱگ‬ར༻Ͱ͖Δɼ৽ͨͳԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾํ๏ΛఏҊͨ͠ɽ• ఏҊख๏Λ࣮૷͠ɼ࣮ࡍͷϓϩάϥϜʹରͯ͠ޮՌΛ֬ೝͨ͠ɽ
Ҏ߱ɼ2 અͰ͸‫ڀݚ‬ͷഎ‫طͯ͠ͱܠ‬ଘͷԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾํ๏ʹ͍ͭͯड़΂Δɽ3 અͰ͸ఏҊख๏Λɼ4 અͰ͸ධՁ࣮‫ݧ‬Λɼ5 અͰ͸ؔ࿈‫ڀݚ‬Λɼ6 અͰ
͸·ͱΊͱࠓ‫ޙ‬ͷ՝୊Λड़΂Δɽ

2

എ‫ܠ‬

2.1 Ծ૝ϝιου‫ͼݺ‬ग़͠ͷղܾํ๏Ծ૝ϝιου‫ͼݺ‬ग़͠ v.m(a1 , a2 , ..., an ) ͕͋Δͱ͖ɼ࣮ߦ࣌ʹ‫ͼݺ‬ग़͞ΕΔϝιου͸ɼม਺ v ͕࣮ߦ࣌ʹࢀর͍ͯ͠ΔΦϒδΣΫτ o ʹ࣮૷͞Ε͍ͯΔ m ͱಉ͡γάωνϟΛ࣋ͭϝιου mtarget Ͱ͋Δɽmtarget ͷ‫ࡧݕ‬͸࣍ͷखॱͰߦ͏ɽo ͷ‫ܕ‬ΛΫϥε C ͱͨ͠ͱ͖ɼC ͷΫϥε֊૚Λࠜʹ޲͔ͬͯ୳ࡧ͢Δɽͦͯ͠࠷ॳʹ‫ ͔ͨͬͭݟ‬m ͱಉ͡γάωνϟΛ࣋ͭϝιου͕ C.mtarget ͱͳΔɽ੩తղੳʹ͓͍ͯɼϨγʔόΦϒδΣΫτ o ΛҰҙʹಛఆ͢Δ͜ͱ͸Ͱ͖ͳ͍ͨ
Ίɼv ͕࣮ߦ࣌ʹࢀর͠͏ΔΦϒδΣΫτͷ‫ܕ‬ͷू߹ runtime types(v) ΛಘΔඞཁ
͕͋Δɽruntime types(v) ͕ಘΒΕͨ‫ޙ‬͸ɼruntime types(v) தͷͦΕͧΕͷ Ci
ͷΫϥε֊૚Λ୳ࡧ͠ɼ‫ͼݺ‬ग़͞Ε͏Δϝιουͷू߹ Ci .mtarget ͕ಘΒΕΔɽҎ্ͷΑ͏ʹɼԾ૝ϝιου‫ͼݺ‬ग़͠ʹ͓͍࣮ͯߦ࣌ʹ‫ͼݺ‬ग़͞ΕΔՄೳੑͷ͋Δϝιουͷू߹Λಛఆ͢Δ࡞‫ۀ‬ΛԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾͱ‫Ϳݺ‬ɽͦͯ͠ɼԾ૝

An approach for virtual method call resolution with an assumption of a variable type

㼍㻝

㼍㻞

㼍㻝

㼍㻞

㼍㻟

㼧㻭㼩

㼧㻭㼩

㼎㻝

㼎㻞

㼎㻝

㼎㻞

㼎㻟

㼧㻮㼩

㼧㻮㼩

㼏

㼍㻟

㼎㻟

㼍㻝

㼍㻞

㼧㻭㼩

㼧㻭㼩

㼎㻝

㼎㻞

㼧㻮㼩

㼧㻮㼩

㼍㻟

㼎㻟

㼍㻝

㼍㻞

㼧㻭㼩

㼧㻭㼩

㼎㻝

㼎㻞

㼎㻟

㼧㻮㻘㻯㼩

㼧㻮㼩

㼧㻭㼩

㼏

㼏

㼏

㼧㻯㼩

㼧㻯㼩

㼧㻯㼩

(a) ϓϩά(b) ϊʔυͱΤοδͷ࡞(c) ReachingTypes ͷ (d) ‫ڧ‬࿈݁੒෼ͷআ‫ڈ‬ϥϜ੒ॳ‫ظ‬ঢ়ଶ㼍㻟(e) ࠷ऴ݁Ռ

ਤ 1: VTA ͷྫϝιου‫ͼݺ‬ग़͠ͷղܾख๏ͱ͸ɼruntime types(v) Λ‫ٻ‬ΊΔख๏ͱߟ͑Δ͜ͱ͕
Ͱ͖Δɽ

2.2 Ϋϥε֊૚ղੳΫϥε֊૚ղੳ͸ɼϨγʔόΦϒδΣΫτͷએ‫ͱܕݴ‬એ‫ܕݴ‬ͷΫϥε֊૚Λ෼ੳ
͠ɼruntime types(v) Λอकతʹ‫ٻ‬ΊΔख๏Ͱ͋Δ [1]ɽΫϥε֊૚ղੳͰ͸ɼม਺v ͷએ‫ܕݴ‬Λ d ͱͨ࣌͠ɼruntimes types(v) ͸ɼv ʹ୅ೖ͞ΕΔΦϒδΣΫτ͕औΓ͏Δ‫ܕ‬ͷू߹ hierarchy types(d) ͱͳΔɽJava ʹ͓͚Δ hierarchy types(d) ͸ҎԼͷΑ͏ʹಘΒΕΔɽ
• d ͕Ϋϥε C ͷ৔߹ɼC ͱ C ͷαϒΫϥε͢΂ͯͷू߹ɽ• d ͕ΠϯλʔϑΣʔε I ͷ৔߹ɼ࣍ͷ 2 ͭͷू߹ͷ࿨ू߹ɽ◦ I ·ͨ͸ I ͷ೿ੜΠϯλʔϑΣΠεΛ࣮૷͍ͯ͠Δ͢΂ͯͷΫϥεͷू߹ɽҎ߱ implements(I) ͱ‫Ϳݺ‬ɽ◦ implements(I) ͷαϒΫϥε͢΂ͯɽΫϥε֊૚ղੳ͸ɼએ‫ܕݴ‬ͷม਺ʹ୅ೖ͞Εͯ΋‫ܕ‬ΤϥʔʹͳΒͳ͍αϒΫϥε
͢΂ͯΛ࿙Εແ͘ runtimes types(v) ʹ௥Ճ͢ΔͨΊɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾ࣌ʹ‫ݺ‬͹ΕΔՄೳੑͷ͋Δϝιου͢΂ͯΛอकతʹऔಘͰ͖Δͱ͍͏ಛ௃͕͋
Δɽ·ͨɼର৅ͷϓϩάϥϜதͷ‫֊ܕ‬૚ߏ଄ͱએ‫͑͞ܕݴ‬෼͔Ε͹ྑ͍ͨΊඇৗʹߴ଎ʹಈ࡞͢Δɽ
2.3 Variable Type Analysis
Variable Type AnalysisʢVTAʣ [3] ͸ɼม਺ؒͷ୅ೖؔ܎΍Ҿ਺౉͠ͷؔ܎Λࣔ͢ Type Propagation GraphʢTPGʣΛ࡞੒͠ɼΦϒδΣΫτͷΞϩέʔγϣϯ͔Βม਺΁ͱ‫఻ܕ‬೻Λߦ͍ɼruntime types(v) Λ‫ٻ‬ΊΔख๏Ͱ͋ΔɽVTA Ͱ͸ TPG
্ʹม਺ʹରԠ͢ΔϊʔυΛ࡞੒͠ɼͦΕͧΕͷϊʔυʹ ReachingTypes ΛׂΓ౰ͯΔɽ͜ͷ ReachingTypes ͕ม਺ʹ୅ೖ͞ΕΔՄೳੑͷ͋ΔΦϒδΣΫτͷ‫ܕ‬ͷू߹Λ͓ࣔͯ͠Γɼruntime types(v) ͸ɼv ʹରԠ͢Δϊʔυͷ ReachingTypes ͱͳ
ΔɽVTA ͸ɼม਺ؒͷ୅ೖؔ܎Λ༻͍ΔͨΊϓϩάϥϜதͰ୅ೖ͞ΕΔՄೳੑͷແ͍αϒΫϥεͷӨ‫ڹ‬Λআ‫͖Ͱڈ‬ΔͨΊɼΫϥε֊૚ղੳΑΓ΋ਫ਼౓ͷߴ͍݁ՌΛಘΒΕΔɽ
2.3.1 Type Propagation Graph ͷ࡞੒ํ๏
TPG ͸༗޲άϥϑͰ͋Γɼϊʔυ͸ϓϩάϥϜதͷม਺ʹରԠͯ͠࡞੒͞ΕɼΤοδ͸ม਺ͷ୅ೖؔ܎΍഑ྻʹΑΔࢀরͷ‫ڞ‬༗ʹରԠͯ͠࡞੒͞ΕΔɽTPG ͷ࡞੒Ͱ͸ɼ·ͣɼΫϥε֊૚ղੳΛ༻͍ͯԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾΛߦ͍ɼίʔϧάϥϑΛ࡞੒͢ΔɽҎ߱͜ͷίʔϧάϥϑΛอकతͳίʔϧάϥϑͱ‫Ϳݺ‬ɽ࣍ʹɼTPG Λ࡞੒͢Δɽ·ͣɼϊʔυΛҎԼͷखॱͰ࡞੒͢ΔɽFOSE2012• ϓϩάϥϜ P ʹ‫·ؚ‬ΕΔ͢΂ͯͷΫϥε C ʹରͯ͠ɼC ͕࣋ͭ͢΂ͯͷΦϒδΣΫτ‫ܕ‬ͷϑΟʔϧυ f ͝ͱʹɼϥϕϧ C.f ͷϊʔυΛ࡞੒͢Δɽ• P ͷอकతͳίʔϧάϥϑதʹग़‫͢ݱ‬Δ͢΂ͯͷϝιου C.m ʹରͯ͠ҎԼͷॲཧΛߦ͏ɽ
◦ C.m ͷΦϒδΣΫτ‫ܕ‬ͷԾҾ਺ pi ͢΂ͯʹରͯ͠ɼϥϕϧ C.m.pi ͷϊʔυΛ࡞੒͢Δɽ◦ C.m ͷΦϒδΣΫτ‫ܕ‬ͷϩʔΧϧม਺ vi ͢΂ͯʹରͯ͠ɼϥϕϧ C.m.viͷϊʔυΛ࡞੒͢Δɽ
◦ C.m ͕੩తϝιουͰ͸ͳ͍৔߹ɼٖࣅม਺ this ʹରԠ͢Δɼϥϕϧ
C.m.this ͷϊʔυΛ࡞੒͢Δɽ
◦ C.m ͕ΦϒδΣΫτ‫ܕ‬ͷ໭Γ஋Λ࣋ͭ৔߹ɼϥϕϧ C.m.return ͷϊʔυΛ࡞੒͢Δɽ
ͦͯ͠ɼΤοδΛҎԼͷखॱͰ࡞੒͢Δɽ• ୅ೖจ lhs = rhs ͕ଘࡏ͠ɼlhs ͱ rhs ͕‫ʹڞ‬ม਺΍ϑΟʔϧυࢀর·ͨ͸഑ྻࢀরͰ͋Δ৔߹ɼrhs தͷม਺Λද͢ϊʔυ͔Βɼlhs தͷม਺Λද͢ϊʔυ΁ͷ༗޲ΤοδΛ௥Ճ͢Δɽ• ୅ೖจ lhs = o.m(a1 , a2 , ..., an )ɼ·ͨ͸ɼϝιου‫ͼݺ‬ग़͠จ o.m(a1 , a2 , ..., an )͕ଘࡏ͠ɼ͜ͷϝιου‫ͼݺ‬ग़͕͠ C.m ͱରԠ͢Δͱ͢Δɽ͜ͷ࣌ɼอकతͳ
ίʔϧάϥϑ্ͰɼC.m ʹΑͬͯ‫ͼݺ‬ग़͞Ε͏Δ͢΂ͯͷϝιου C  .m ʹରͯ͠ɼҎԼͷखॱͰΤοδΛ௥Ճ͢Δɽ◦ o ʹରԠ͢Δϊʔυ͔Β C  .m .this ʹରԠ͢Δϊʔυ΁ͷΤοδΛ௥Ճ͢Δɽ◦ C  .m ͷ໭Γ஋͕ void Ͱͳ͍৔߹ɼC  .m .return ͔Β lhs ʹରԠ͢Δϊʔυ΁ͷΤοδΛ௥Ճ͢Δɽ◦ ΦϒδΣΫτ‫ܕ‬ͷ࣮Ҿ਺ aj ʹରͯ͠͸ɼaj ʹରԠ͢Δϊʔυ͔Β C  .m ͷ
aj ͱରԠ͢ΔԾҾ਺ͷϊʔυ΁ͱΤοδΛ௥Ճ͢Δɽ
ਤ 1b ͸ɼਤ 1a ͷιʔείʔυ͔Β TPG Λੜ੒ͨ͠ྫͰ͋Δɽ֤ม਺ʹରԠ͢Δϊʔυ͕࡞੒͞Εɼ୅ೖจʹซͤͯ༗޲Τοδ͕࡞੒͞Ε͍ͯΔɽ
2.3.2
‫఻ܕ‬೻
TPG ͷ࡞੒‫ޙ‬ɼ֤ϊʔυͷ ReachingTypes Λ‫ٻ‬ΊΔɽ·ͣɼશϊʔυʹۭू߹ͷ ReachingTypes ΛׂΓ౰ͯΔɽ
ͦͯ͠ɼlhs = newA(); ·ͨ͸ɼlhs = newA[n]; ͱ͍͏ΞϩέʔγϣϯΛߦ͏୅ೖจʹରͯ͠ɼlhs ʹରԠ͢Δม਺ͷϊʔυͷ ReachingTypes ʹ A Λ௥Ճ͢Δɽ࣍
ʹɼղੳର৅֎ͷϝιουͷ‫ͼݺ‬ग़͠จ lhs = o.m(a1 , a2 , ..., an ) ʹ͍ͭͯ͸ɼm ͷએ‫࣌ݴ‬ͷ໭Γ஋ͷ‫ܕ‬ͷαϒΫϥε͢΂ͯΛ lhs ͷ ReachingTypes ʹ௥Ճ͢Δɽಉ༷
ʹɼղੳର৅֎ͷϑΟʔϧυΛ༻͍ͨ୅ೖจ lhs = o.f ʹ͍ͭͯ͸ɼf ͷαϒΫϥ
ε͢΂ͯΛ lhs ͷ ReachingTypes ʹ௥Ճ͢Δɽਤ 1c ͸ɼਤ 1b ʹɼReachingTypes
ΛׂΓ౰ͯͨ΋ͷͰɼਤ 1a தͷม਺΁ͷΞϩέʔγϣϯΛߦ͍ͬͯΔจʹซͤͯ
ReachingTypes Λ௥Ճ͍ͯ͠Δɽ
࣍ʹɼTPG ্ͷ‫ڧ‬࿈݁੒෼Λ‫͠ࡧݕ‬ɼ‫ڧ‬࿈݁੒෼தͷϊʔυΛ 1 ͭͷεʔύʔϊʔυʹม‫͢׵‬Δɽεʔύʔϊʔυͷ ReachingTypes ͸‫ڧ‬࿈݁੒෼தͷϊʔυͷ
ReachingTypes ͷ࿨ू߹ͱ͠ɼҎ‫ޙ‬εʔύʔϊʔυதͷϊʔυͷ ReachingTypes ͸ɼεʔύʔϊʔυͷ ReachingTypes ͱ͢Δɽͳ͓ɼ‫ڧ‬࿈݁੒෼ͷંΓͨͨΈΛߦͬͨ‫ޙ‬ͷ TPG ͸ɼແด࿏༗޲άϥϑʢDAGʣͱͳΔɽਤ 1c ͸ɼਤ 1b ʹରͯ͠‫ڧ‬࿈݁੒෼ͷંΓͨͨΈΛߦͬͨྫͰ͋Δɽਤதͷ b3 ͱ a3 ͸‫ڧ‬࿈݁੒෼Ͱ͋Γɼ͜ͷ 2ͭͷϊʔυΛεʔύʔϊʔυ΁ͱม‫͍ͯ͠׵‬Δɽ࠷‫ʹޙ‬ɼDAG ʹม‫ ͨ͠׵‬TPG ͷϊʔυؒͰτϙϩδΧϧιʔτΛ࣮ߦ͠ɼReachingTypes ͷ఻೻Λߦ͏ɽ۩ମతʹ͸ɼ֤Τοδ na → nb ʹରͯ͠ɼnb ͷ ReachingTypes Λ na ͷ ReachingTypes ͱͷ࿨ू߹ͱ͢Δɽਤ 1e ͸ɼਤ 1d ͷ TPG ʹର͠
ReachingTypes ͷ఻೻ΛߦͬͨྫͰ͋Δɽ͜ͷ݁Ռɼb1 ͷ ReachingTypes ͸ɼb2 ͱ
c ͷ ReachingTypes ͷ࿨ू߹ͱͳΓɼ{B,C} ͱͳ͍ͬͯΔɽ·ͨɼa3 ͱ b3 ͷεʔAn approach for virtual method call resolution with an assumption of a variable typeύʔϊʔυʹ͸ɼa1 ͔Β‫ܕ‬ͷ఻೻͕ߦΘΕɼReachingTypes ͸ {A} ͱͳΔɽ

3

ఏҊख๏

ఏҊख๏͸ɼ༩͑ΒΕͨ Java ϓϩάϥϜʹ͓͍ͯɼม਺ va ʹ֨ೲ͞ΕΔΦϒδΣΫτΛಛఆͷ‫ ܕ‬Cf ixed ͱԾఆͨ͠৔߹ͷԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾΛߦ͏ɽఏҊख๏͸࣍ͷ 3 ͭͷεςοϓͰߏ੒͞ΕΔɽ
εςοϓ 1 ϓϩάϥϜશମʹରͯ͠ VTA Λߦ͍ɼTPG Λ࡞੒͢Δɽ
εςοϓ 2 va ʹґଘͯ͠‫·ܾ͕ܕ‬Δม਺ͷू߹Λ‫ٻ‬ΊΔɽεςοϓ 3 va ͕ϨγʔόΦϒδΣΫτͱͳΔϝιου‫ͼݺ‬ग़͠Λಛఆ͠ɼରԠ͢Δ TPG ্ͷΤοδΛআ‫͢ڈ‬Δɽͦͯ͠ɼ‫఻ܕ‬೻Λߦ͍ ReachingT ypes Λ‫ٻ‬ΊΔɽ݁Ռ‫·ٻ‬Δ v ͷ ReachingT ypes ͕ runtime types(v) Ͱ͋ΔɽҎ߱ɼεςοϓ 2 ͱεςοϓ 3 ʹ͍ͭͯղઆ͢Δɽ

3.1 εςοϓ 2: ࢦఆͨ͠ม਺ʹґଘͯ͠‫·ܾ͕ܕ‬Δม਺ͷಛఆεςοϓ 2 Ͱ͸ɼม਺ va ͷ‫ʹܕ‬ґଘͯ͠‫·ܾ͕ܕ‬Δม਺ɼ͢ͳΘͪɼม਺ va Ҏ֎ʹ‫఻͕ܕ‬೻͞ΕΔ͜ͱ͕ແ͍ม਺ͷू߹Λ‫ٻ‬ΊΔɻ۩ମతʹ͸ɼva ʹରԠ͢ΔϊʔυΛ na ͱͨ͠ͱ͖ɺ࣍ͷ 2 ͭͷखॱͰ‫·ٻ‬Δϊʔυू߹ Nd ʹରԠ͢Δม਺ͷू߹Λࢦ͢ɽ
खॱ 1 Nd ← {na } ͱ͢Δɽ
खॱ 2 Nd ← Nd ∪ {n|p(n) ⊆ Nd } Λ Nd ͕มԽ͠ͳ͘ͳΔ·Ͱߦ͏ɽͨͩ͠ɺp(n)͸ϊʔυ n ʹର͢Δ༗ޮล n → n Λ࣋ͭϊʔυ n’ ͷू߹Ͱ͋Δɽ
ਤ 2a ͷϓϩάϥϜʹରͯ͠࡞੒ͨ͠ TPG ͷҰ෦͕ਤ 2b Ͱ͋Δɽ͜͜ͰɼΫϥε M ͷϑΟʔϧυ f ͷ‫ܕ‬Λ B ʹ‫ݻ‬ఆͨ͠ͱ͢ΔͱɼNd = {M.f, M.g.j} Ͱ͋Γɼ
M.g.j ͷ‫ܕ‬΋ B ʹ‫ݻ‬ఆ͞ΕΔɽ
3.2 εςοϓ 3: TPG ͷՃ޻ͱ‫఻ܕ‬೻v ∈ Nd ͱͳΔԾ૝ϝιου‫ͼݺ‬ग़͠ v.m ͸ɼva ͷ‫ʹܕ‬ґଘ͍ͯ͠ΔͨΊɼv.mͰ‫ݺ‬͹ΕΔϝιου͸ɼCf ixed ͷΫϥε֊૚Λ୳ࡧͯ͠ಘΒΕΔɼm ͱಉ͡γάωνϟΛ࣋ͭϝιου mf ixed target ͱಛఆͰ͖ɼଞͷϝιου͸‫ݺ‬͹Εͳ͍͜ͱ͕෼
͔ΔɽҎ্ͷ݁Ռ͔Βίʔϧάϥϑ͕มԽ͠ɼϝιου‫ͼݺ‬ग़͠ʹରԠ͍ͯͨ͠ΤοδΛ TPG ͔Βআ‫͢ڈ‬Δ͜ͱ͕Ͱ͖Δɽ࠷‫ʹޙ‬ɼ‫఻ܕ‬೻Λߦ͍ ReachingTypes Λ‫ٻ‬ΊΔɽΤοδͷআ‫ڈ‬͸ɼҎԼͷΑ͏ʹߦ͏ɽ• vʢ∈ Nd ʣ͕ϨγʔόΦϒδΣΫτͱͳΔԾ૝ϝιου‫ͼݺ‬ग़͠ v.m(a1 , a2 , ...an )ʹ͍ͭͯɼ◦ ‫ͼݺ‬ग़͞ΕΔϝιουͷީิͰ͋ͬͨɼCf ixed .m Ҏ֎ͷ C.m ʹରͯ͠ɼ∗ v ʹରԠ͢Δϊʔυ͔Β C.m.this ʹରԠ͢Δϊʔυ΁ͷΤοδΛ࡟আɽ∗ ࣮Ҿ਺ aj ʹରԠ͢Δϊʔυ͔ΒɼԾҾ਺ C.m.fj ʹରԠ͢Δϊʔυ΁ͷΤοδΛ࡟আ
∗ C.m.return ͔Βɼ໭Γ஋Λड͚औΔม਺ʹରԠ͢Δϊʔυ΁ͷΤοδ
Λ࡟আͦͯ͠ɼΤοδআ‫ޙڈ‬ͷ TPG Λ༻͍ͯ‫఻ܕ‬೻Λߦ͍ɼશม਺ͷ ReachingT ypesΛ‫ٻ‬ΊΔɽͨͩ͠ɼNd ʹଐ͢Δม਺ͷ ReachingT ypes ͸ Cf ixed ͷΈͱ͢Δɽ
ਤ 2b ͷྫͰɼ‫ܕ‬ΛԾఆ͠ Nd Λ‫ٻ‬Ί͕ͨɼ͜ͷ݁Ռ M.g.j ͕ϨγʔόΦϒδΣΫτͱͳΔ 18 ߦ໨ͷϝιου‫ͼݺ‬ग़͠ i.r() Ͱ‫ͼݺ‬ग़͞ΕΔϝιου͸ɼB.r() ͷΈͱͳΔɽΑͬͯਤ 2c ʹࣔ͢ͱ͓Γɼi.r() ͷ໭Γ஋ʹΑΔΤοδͰ͋Δ A.r.return →M.g.i ͱ C.r.return → M.g.i Λআ‫͢ڈ‬Δɽͦͯ͠ɼਤ 2d ͕‫఻ܕ‬೻Λߦͬͨ݁ՌͰ
͋ΓɼM.g.i ͷ ReachingT ypes ͸ TI ͷΈͱͳΔɽ͜ͷ݁Ռɼ19 ߦ໨ͷԾ૝ϝιου‫ͼݺ‬ग़͠ i.p() ͷղܾ݁Ռ͸ɼT I.p() ͷΈͱͳΔɽ

FOSE2012㻝㻦㻌㼏㼘㼍㼟㼟㻌㻭㻌㼧㻌㻞㻦㻌㻵㻌㼞㻔㻕㻌㼧㻌㼞㼑㼠㼡㼞㼚㻌㼚㼑㼣㻌㻵㻔㻕㻧㻌㼩㻌㼩㻟㻦㻌㼏㼘㼍㼟㼟㻌㻮㻌㼑㼤㼠㼑㼚㼐㼟㻌㻭㻌㼧㻠㻦㻌㻵㻌㼞㻔㻕㻌㼧㻌㼞㼑㼠㼡㼞㼚㻌㼚㼑㼣㻌㼀㻵㻔㻕㻧㻌㼩㻌㼩㻡㻦㻌㼏㼘㼍㼟㼟㻌㻯㻌㼑㼤㼠㼑㼚㼐㼟㻌㻭㻌㼧㻢㻦㻌㻵㻌㼞㻔㻕㻌㼧㻌㼞㼑㼠㼡㼞㼚㻌㻌㼚㼑㼣㻌㻾㻵㻔㻕㻧㻌㼩㻌㼩㻣㻦㻌㻤㻦㻌㻌㼏㼘㼍㼟㼟㻌㻵㻭㻌㼧㻌㼢㼛㼕㼐㻌㼜㻔㻕㻌㼧㻌㻚㻚㻚㻌㼩㻧㻌㼩㻥㻦㻌㻌㼏㼘㼍㼟㼟㻌㼀㻵㻌㼑㼤㼠㼑㼚㼐㼟㻌㻵㻌㼧㻌㼢㼛㼕㼐㻌㼜㻔㻕㻌㼧㻌㻚㻚㻚㻌㼩㻌㼩㻝㻜㻦㻌㼏㼘㼍㼟㼟㻌㻾㻵㻌㼑㼤㼠㼑㼚㼐㼟㻌㻵㻌㼧㻌㼢㼛㼕㼐㻌㼜㻔㻕㻌㼧㻌㻚㻚㻚㻌㼩㻌㼩㻝㻝㻦㻌㻝㻞㻦㻌㼏㼘㼍㼟㼟㻌㻹㻌㼧
㻝㻟㻦㻌
㻭㻌㼒㻧
㻝㻠㻦㻌
㼢㼛㼕㼐㻌㼟㼑㼠㻮㻔㻕㻌㼧㻌㼠㼔㼕㼟㻚㼒 㻩㻌㼚㼑㼣㻌㻮㻔㻕㻧㻌㼩㻝㻡㻦㻌㼢㼛㼕㼐㻌㼟㼑㼠㻯㻔㻕㻌㼧㻌㼠㼔㼕㼟㻚㼒 㻩㻌㼚㼑㼣㻌㻯㻔㻕㻧㻌㼩㻝㻢㻦㻌㼢㼛㼕㼐㻌㼓㻔㻕㻌㼧㻝㻣㻦㻌㻭㻌㼖㻌㻩㻌㼒㻧㻝㻤㻦㻌㻵㻌㼕 㻩㻌㼖㻚㼞㻔㻕㻧㻝㻥㻦㻌㼕㻚㼜㻔㻕㻧
㻞㻜㻦㻌
㼩
㻞㻝㻦㻌㼩

(a) ϓϩάϥϜ

㻹㻚㼒

㻹㻚㼓㻚㼖

㻹㻚㼒

㻹㻚㼓㻚㼖

㻹㻚㼒

㻹㻚㼓㻚㼖

㼧㻮㻘㻯㼩

㼧㻮㻘㻌㻯㼩

㼧㻮㼩

㼧㻮㼩

㼧㻮㼩

㼧㻮㼩

㻭㻚㼞㻚㼞㼑㼠㼡㼞㼚㻭㻚㼞㻚㼞㼑㼠㼡㼞㼚㻭㻚㼞㻚㼞㼑㼠㼡㼞㼚

㼧㻵㼩

㼧㻵㼩

㼧㻵㼩

㻮㻚㼞㻚㼞㼑㼠㼡㼞㼚㻹㻚㼓㻚㼕㻮㻚㼞㻚㼞㼑㼠㼡㼞㼚㻹㻚㼓㻚㼕㻮㻚㼞㻚㼞㼑㼠㼡㼞㼚

㻹㻚㼓㻚㼕

㼧㼀㻵㼩

㼧㻵㻘㻌㼀㻵㻘㻌㻾㻵㼩㼧㼀㻵㼩㼧㻵㻘㼀㻵㻘㻾㻵㼩

㼧㼀㻵㼩

㼧㼀㻵㼩

㻯㻚㼞㻚㼞㼑㼠㼡㼞㼚㻯㻚㼞㻚㼞㼑㼠㼡㼞㼚㻯㻚㼞㻚㼞㼑㼠㼡㼞㼚

㼧㻾㻵㼩

㼧㻾㻵㼩

㼧㻾㻵㼩

(b) ॳ‫ظ‬ͷ TPG(c) มԽ‫ޙ‬ͷ TPG(d) ࠶౓ͷ‫఻ܕ‬೻‫ޙ‬ਤ 2: ఏҊख๏ͷྫද 1: ࣮‫ݧ‬ର৅ͷϓϩάϥϜ
ϓϩάϥϜ໊ANTLR
Apache-AntʢANT)
Apache-TomcatʢTomcat)
Batik
JEdit
࿨Վࢁେֶ‫ڭ‬຿γεςϜ (KS)Torque

4

Ϋϥε਺
1,201
1,286
2,681
5,236
1,132
4,446
2,589

ϝιου਺
11,971
11,54928,462
41,557
7,998
41,10624,975Ծ૝ϝιου‫ͼݺ‬ग़͠਺
14,616
15,97236,50549,825
17,516
46,84825,267࣮‫ݧ‬ఏҊख๏Λ࣮૷͠ɼޮՌΛௐࠪ͢ΔͨΊධՁ࣮‫ݧ‬Λߦͬͨɽ࣮‫ͯͬͨ͋ʹݧ‬ҎԼͷϦαʔνΫΤενϣϯʢRQʣΛઃఆͨ͠ɽ
RQ1 ֨ೲ͞ΕΔ͞ΕΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆ͢Δ͜ͱͰɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾʹӨ‫ڹ‬Λ༩͑ΔՄೳੑͷ͋Δม਺͸͍ͭ͋͘Δͷ͔
RQ2 ม਺͕Ծ૝ϝιου‫ͼݺ‬ग़͠ͷղܾʹӨ‫ڹ‬Λ༩͍͑ͯΔ৔߹ɼ1 ͭͷม਺͋ͨΓ͍ͭ͘ͷϝιου‫ͼݺ‬ग़͠ʹӨ‫ڹ‬Λ༩͍͑ͯΔͷ͔
RQ3 ఏҊख๏Λ༻͍ͨ݁Ռɼ‫ط‬ଘख๏ͱൺ΂ͯίʔϧάϥϑ͸ͲͷΑ͏ʹมԽ͢Δͷ͔࣮‫ݧ‬ର৅ͱͨ͠ͷ͸ද 1 ʹࣔ͢ 7 ‫ݸ‬ͷ Java ϓϩάϥϜͰ͋Δɽද 1 ʹɼ֤ϓϩάϥϜͷΫϥε਺ɼϝιου਺ɼԾ૝ϝιου‫ͼݺ‬ग़͠਺΋ซ͍ͤͯࣔͯ͠Δɽ
ௐࠪର৅ͱͨ͠ม਺͸ɼԾҾ਺ʢϨγʔόΦϒδΣΫτ΋‫ؚ‬ΉʣɼϑΟʔϧυɼͦͯ͠ϩʔΧϧม਺ͷ 3 छྨͰ͋ΔɽͦΕΒͷม਺Λର৅ʹҎԼͷௐࠪΛߦͬͨɽ
1. ReachingTypes ͕ෳ਺͋Δม਺Λ਺͑Δ ɽ
ʢRQ1 ʹରԠʣ
2. ReachingTypes ͕‫ܕ‬Λෳ਺‫ؚ‬Ήม਺Λର৅ʹɼͦͷม਺ʹґଘͯ͠‫·ܾ͕ܕ‬Δ
ม਺ͷू߹ Nd Λಛఆ͠ɼNd ʹ‫·ؚ‬ΕΔม਺ΛϨγʔόΦϒδΣΫτͱ͢ΔԾ
૝ϝιου‫ͼݺ‬ग़͠Λಛఆ͢ΔɽͦͷԾ૝ϝιου‫ͼݺ‬ग़͠ʹ͍ͭͯɼϝιου‫ͼݺ‬ग़͠ͷީิ਺Λௐࠪ͠ɼෳ਺ͷީิ͕‫͔ͨͬͭݟ‬Ծ૝ϝιου‫ͼݺ‬ग़͠Λ਺্͑͛Δɽ·ͨɼͦͷΑ͏ͳԾ૝ϝιου‫ͼݺ‬ग़͕͠‫͔ͭݟ‬Δม਺ʹ͍ͭͯ΋਺্͑͛ΔɽʢRQ1ɼRQ2 ʹରԠʣ
3. ϝιου‫ͼݺ‬ग़͠ͷީิ਺͕ෳ਺͋ΔԾ૝ϝιου‫ͼݺ‬ग़͕͠‫͔ͨͬͭݟ‬৔߹ɼม਺ v ͷΦϒδΣΫτͷ‫ܕ‬Λ ReachingTypes ʹ‫·ؚ‬ΕΔ‫ܕ‬ͷ 1 ͭͱԾఆ͠ɼఏ
Ҋख๏Λ༻͍ͯԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾΛߦ͍ɼ‫ݩ‬ͷίʔϧάϥϑ͔Βআ‫͞ڈ‬ΕͨϊʔυͱΤοδΛ਺্͑͛Δɽ
ʢRQ3 ʹରԠʣ਺্͑͛Λߦ͏ࡍͷίʔϧάϥϑͷϊʔυͱΤοδ͸࣍ͷΑ͏ʹఆٛ͢Δɽϊʔυ͸ϝιουʹରԠ͢Δ΋ͷͱ͠ɼଞͷϝιουΛ‫ͼݺ‬ग़͍ͯ͠Δɼ·ͨ͸ɼଞͷϝιου͔Β‫ͼݺ‬ग़͞Ε͍ͯΔ΋ͷΛ਺্͑͛ΔɽΤοδ͸ϝιου‫ͼݺ‬ग़͠ʹର

An approach for virtual method call resolution with an assumption of a variable type

ද 2: Ծ૝ϝιου‫ͼݺ‬ग़͠ʹӨ‫ڹ‬Λ༩͑Δม਺

ant

batik

Ө‫ڹ‬༗Γ
680 (3.5%)
873 (4.7%)
2,077 (4.4%)
2,077 (3.0%)
163 (1.3%)
2,158 (3.0%)756 (1.8%)ϑΟʔϧυෳ਺ͷ‫ܕ‬
121 (3.4%)
155 (3.6%)
348 (4.3%)
933 (4.4%)
137 (5.1%)
873 (8.3%)
345 (6.0%)

૯਺
3,552
4,317
8,155
21,2842,670
10,4815,710

Ө‫ڹ‬༗Γ
42 (1.2%)
64 (1.5%)
136 (1.7%)
297 (1.4%)
45 (1.7%)542 (5.2%)
145 (2.5%)ϩʔΧϧม਺
ෳ਺ͷ‫ܕ‬
386 (2.6%)345 (3.8%)
1,054 (4.3%)
1,829 (6.0%)
192 (2.9%)
1,082 (4.1%)
747 (5.1%)

Ө‫ڹ‬༗Γ133 (0.9%)
165 (1.8%)272 (1.1%)
835 (2.7%)
59 (0.9%)427 (1.6%)
211 (1.4%)

1500

1000
0

0

200

500

400

600

1000

800

1000
0

200

400

600

800

૯਺
14,794
9,030
24,42530,567
6,698
26,40814,7312000ԾҾ਺ෳ਺ͷ‫ܕ‬
2,731 (14%)
2,420 (13%)
7,700 (16%)
11,997 (17%)
1,331 (10%)
9,715 (14%)
4,841(12%)

1200

૯਺
19,487
18,496
46,79369,093
12,907
71,25340,964

1200

ANTLR
Ant
Tomcat
Batik
JEdit
KS
Torqueantlr

tomcatjedit(a) ԾҾ਺KS

Torqueantlr

ant

tomcat

batik

jedit

KS

Torque(b) ϑΟʔϧυ

antlr

ant

tomcat

batik

jedit

KS

(c) ϩʔΧϧม਺ਤ 3: Ө‫ڹ‬Λड͚ΔԾ૝ϝιου‫ͼݺ‬ग़͠਺ͷ෼෍Ԡ͢Δ΋ͷͱ͠ɼ‫ͼݺ‬ग़͠จ͝ͱʹ‫ݸ‬ผʹϝιουؒʹΤοδΛҾ͘΋ͷͱ͢Δɽ
ϝιου m ͷ͋Δ‫ͼݺ‬ग़͠จͰɼϝιου g Λ‫ͼݺ‬ग़͍ͯ͠Δ৔߹ɼm ʹରԠ͢Δϊʔυ͔Β g ʹରԠ͢ΔϊʔυʹΤοδΛҾ͘ɽෳ਺ͷ‫ͼݺ‬ग़͠จ͕ଘࡏ͢Δ৔߹͸ɼจͷ਺͚ͩΤοδΛҾ͘ɽ

4.1
࣮‫݁ݧ‬Ռ
4.1.1 RQ1 ʹର͢Δ࣮‫݁ݧ‬Ռͱճ౴
RQ1 ʹରԠͨ͠ௐࠪΛߦͬͨ݁ՌΛද 2 ʹࣔ͢ɽද 2 ʹ͸ɼԾҾ਺ɼϑΟʔϧυɼϩʔΧϧม਺ͷͦΕͧΕʹ͍ͭͯɼΦϒδΣΫτ‫ܕ‬ͷม਺ͷ૯਺ͱɼͦͷ͏ͪ
ReachingTypes ʹෳ਺ͷ‫·ؚ͕ܕ‬ΕΔ΋ͷͷ਺ʢʮෳ਺ͷ‫ܕ‬ʯྻʣɼͦΕΒͷม਺ͷ͏ͪԾ૝ϝιου‫ͼݺ‬ग़͠ʹ࢖༻͞Εɼ͔ͭɼͦͷԾ૝ϝιου‫ͼݺ‬ग़͠ʹෳ਺ͷϝιου‫ͼݺ‬ग़͠ީิ͕ଘࡏ͢Δ΋ͷͷ਺ʢʮӨ‫ڹ‬༗ΓʯྻʣΛ͍ࣔͯ͠Δɽͳ͓ɼදதͷ‫಺ހׅ‬ͷ਺஋͸ɼ૯਺ʹର͢Δׂ߹Λ͍ࣔͯ͠Δɽ
ද 2 ΑΓɼෳ਺ͷ‫ ͕ܕ‬ReachingTypes ʹ‫·ؚ‬ΕΔม਺͸ɼશମʹൺͯ͠ԾҾ਺ͷ৔߹͸ 10%͔Β 17%ɼϑΟʔϧυ΍ϩʔΧϧม਺ͷ৔߹͸ 2.6%͔Β 8.3%Ͱ͋ͬͨɽ
͜ͷ݁Ռ͔Βɼෳ਺ͷ‫ܕ‬ΛऔΓ͏Δม਺͸ɼׂ߹ͱͯ͠͸શମʹൺͯ͠গ਺Ͱ͋Δ
͜ͱ͕Θ͔Δɽ·ͨɼෳ਺ͷ‫·ؚ͕ܕ‬Εɼ͞Βʹϝιου‫ͼݺ‬ग़͠ʹӨ‫ڹ‬Λ༩͑ΔΑ͏ͳม਺͸શମʹൺͯ͠ඇৗʹগ਺Ͱ͋ΓɼԾҾ਺ͱϑΟʔϧυͰ͸ 1 ͭΛআ͖͢΂ͯ 5%Λ
ԼճΓɼϩʔΧϧม਺ͷ৔߹͸͢΂ͯ 3%ҎԼͱ͍͏ׂ߹ʹͳ͍ͬͯΔɽҎ্͔Β‫ܕ‬ͷԾఆʹΑΓίʔϧάϥϑ͕มԽ͢ΔՄೳੑͷ͋Δม਺͸ɼશମʹൺͨ͠৔߹ʹ͸ඇৗʹগ਺Ͱ͋Δ͜ͱ͕෼͔Δɽ
4.1.2 RQ2 ʹର͢Δ࣮‫݁ݧ‬Ռͱճ౴࣍ʹ RQ2 ʹରԠ͢ΔௐࠪΛߦͬͨ݁ՌΛਤ 3 ͱද 3 ʹࣔ͢ɽਤ 3 ͸ɼม਺ͷ‫ܕ‬ͷ‫ݻ‬ఆʹΑΓӨ‫ڹ‬Λड͚ΔԾ૝ϝιου‫ͼݺ‬ग़͠਺ͷ෼෍Λശͻ͛ਤͰ͍ࣔͯ͠Δɽ
ද 3 ͸ɼਤ 3 Ͱࣔͨ͠஋ͷதԝ஋ͱฏ‫ۉ‬஋Λ͍ࣔͯ͠Δɽ
1 ͭͷม਺ͷ‫ܕ‬Λ‫ݻ‬ఆͨ͠৔߹ʹɼ‫ͼݺ‬ग़͞ΕΔՄೳੑͷ͋Δϝιουͷީิ͕ม

TorqueFOSE2012ද 3: Ө‫ڹ‬Λड͚ΔԾ૝ϝιου‫ͼݺ‬ग़͠਺ͷฏ‫ۉ‬஋ͱதԝ஋
ANTLR
Ant
Tomcat
Batik
JEdit
KS
Torque

ԾҾ਺
தԝ஋
ฏ‫ۉ‬஋
1
9.323
6
11.41
13
93.8
4
19.15
2
3.92
3
85.41
8
51

ϑΟʔϧυ
தԝ஋
ฏ‫ۉ‬஋
5.5
44.93
3.5
5.906
5
16.47
4
20.15
3
4.089
3
15.32
6
75.48

ϩʔΧϧม਺
தԝ஋
ฏ‫ۉ‬஋
4
15.83
2
3.564
2
12.86
3
18.48
1
4.051
2
19.39
3
171.7

ද 4: ‫ط‬ଘख๏ʹΑΔίʔϧάϥϑ
ANTLR
Ant
Tomcat
Batik
JEdit
KS
TorqueΫϥε֊૚ղੳ
ϊʔυ਺Τοδ਺
10,101
62,463
9,246
32,26322,701
131,544
31,809207,412
7,151
23,816
31,959123,136
18,85077,045

VTA
ϊʔυ਺
Τοδ਺
8,057
38,029
7,751
19,10918,57260,00525,92878,5506,463
18,19525,97374,381
14,24932,926

ද 5: ϊʔυ‫ݮ‬গྔͱΤοδ‫ݮ‬গྔͷฏ‫ۉ‬஋ͱதԝ஋
ANTLR
Ant
Tomcat
Batik
JEdit
KS
TorqueԾҾ਺আ‫ڈ‬ϊʔυ਺আ‫ڈ‬Τοδ਺
தԝ஋
ฏ‫ۉ‬஋
தԝ஋
ฏ‫ۉ‬஋
1
43.91
53
526.9
3
146.3
69
1044
31
385.1
548
1954
7
464.8
105
2647
0
41.84
8
225.1
2
326.63
48
1880
14
509.4
168
1830

ϑΟʔϧυ
আ‫ڈ‬ϊʔυ਺আ‫ڈ‬Τοδ਺
தԝ஋
ฏ‫ۉ‬஋
தԝ஋
ฏ‫ۉ‬஋
13
133
840
1666
2
38.29
13
268
3
531.3
50.5
2386.8
5
290.5
44
1587
6
14.77
42
51.69
2
355.9
30
2067.8
3
245.1
42
1007

ϩʔΧϧม਺
আ‫ڈ‬ϊʔυ਺আ‫ڈ‬Τοδ਺
தԝ஋
ฏ‫ۉ‬஋
தԝ஋
ฏ‫ۉ‬஋
13
140.8
592
1500.9
1
25.58
11
181.2
1
309.5
27
1429
1
493.2
21
2622
1
16.33
6
77.22
11
529
75
3073
2
472.7
18
1575

Խ͢ΔΑ͏ͳɼԾ૝ϝιου‫ͼݺ‬ग़͠ͷ਺͸ɼਤ 2 ʹࣔ͞ΕΔͷ෼෍ͷ‫ܗ‬ঢ়ͱɼද
3 ʹ͍ࣔͯ͠Δதԝ஋ͷ஋͔Βɼଟ͘ͷ৔߹਺‫͋Ͱݸ‬Δ͜ͱ͕෼͔Δɽ
ͨͩ͠ɼ͜ͷ஋͸ඇৗʹ෼ࢄ͕େ͖͘ɼྫ͑͹ Torque ͷԾҾ਺Ͱ͸ɼ࠷େ஋ͱ͠
ͯ 1200 ‫ݸ‬Ҏ্ͷԾ૝ϝιου‫ͼݺ‬ग़͠ʹӨ‫ڹ‬Λ༩͑Δม਺͕ଘࡏ͢Δ͜ͱ͕ਤ 3a͔Β෼͔ΔɽͦͷͨΊɼద੾ͳม਺Λબ୒͢Δ͜ͱͰɼଟ͘ͷԾ૝ϝιου‫ͼݺ‬ग़͠ʹରͯ͠Ө‫ڹ‬Λ༩͑Δ͜ͱ͕Ͱ͖Δͱߟ͑ΒΕΔɽ
4.1.3 RQ3 ʹର͢Δ࣮‫݁ݧ‬Ռͱճ౴࠷‫ʹޙ‬ɼRQ3 ʹରԠ͢ΔௐࠪΛߦͬͨ݁ՌΛࣔ͢ɽ·ͣɼද 4 ʹɼΫϥε֊૚ղੳΛ༻͍ͯ࡞੒ͨ͠ίʔϧάϥϑͱɼVTA Λ༻͍ͯ࡞੒ͨ͠ίʔϧάϥϑʹ͍ͭͯɼϊʔυ਺ͱΤοδ਺Λࣔ͢ɽ࣍ʹɼਤ 4 ͱਤ 5 ʹɼϝιου‫ͼݺ‬ग़͠ʹӨ‫ڹ‬Λ༩͑ΔΑ͏ͳม਺Λର৅ʹ 1 ͭͷ‫ݻʹܕ‬ఆͨ͠৔߹ͷɼVTA ͷίʔϧάϥϑͱൺֱͨ͠৔߹ͷϊʔυͱΤοδͷ‫ݮ‬গྔͷ෼෍ʹ͍ͭͯͦΕͧΕࣔ͢ɽ·ͨɼද 5 ʹɼ
ਤ 4 ͱਤ 5 ʹࣔͨ͠஋ͷதԝ஋ͱฏ‫ۉ‬஋Λࣔ͢ɽ
͋Δ 1 ͭͷม਺ͷ‫ܕ‬Λ͋Δ 1 ͭͷ‫ݻʹܕ‬ఆ͠ɼ͔ͭɼϝιου‫ͼݺ‬ग़͠ީิΛ‫ݮ‬গͤ͞Δ͜ͱ͕Ͱ͖ͨ৔߹ɼίʔϧάϥϑͷαΠζΛ‫ݮ‬গͤ͞Δ͜ͱ͕Ͱ͖ͨɽಛ
ʹΤοδ਺ʹ͍ͭͯ͸ɼJEdit ͷ৔߹Ҏ֎Ͱɼଟ͘ͷ৔߹਺ेຊҎ্ͷΤοδΛআ‫ڈ‬Ͱ͖ͨ͜ͱ͕ද 5 ͷআ‫ڈ‬Τοδ਺ͷதԝ஋͔Β෼͔Δɽ·ͨɼਤ 4 ͱਤ 5 ͔ΒίʔϧάϥϑͷαΠζ͕େ͖͘‫ݮ‬গͤ͞ΔΑ͏ͳ৔߹͕͋Δ͜ͱ͕෼͔ΓɼͦͷΑ͏ͳม਺ʹରͯ͠‫ܕ‬ͷࢦఆΛߦͬͨ৔߹ɼఏҊख๏͸༗ޮʹಇ͘ͱߟ͑ΒΕΔɽ

4.2 ଥ౰ੑ΁ͷ‫ڴ‬Җࠓճ࣮‫ݧ‬ର৅ʹͨ͠ϓϩάϥϜ͸࣮༻తͳαΠζͷϓϩάϥϜͰ͋Γɼ࣮‫ݧ‬ର৅ͷ‫ن‬໛ʹ͍ͭͯ͸ଥ౰Ͱ͋Δͱߟ͑ΒΕΔɽͨͩ͠ɼ࣮‫ݧ‬ର৅ͱͨ͠ϓϩάϥϜͷ
‫਺ݸ‬͸ɼߴʑ7 ‫͋Ͱݸ‬Γɼର৅ͷϓϩάϥϜΛ૿΍͢͜ͱͰ݁࿦͕มΘΔՄೳੑ͕͋Δɽ
·ͨɼࠓճର৅ʹͨ͠ϓϩάϥϜ͸‫׬‬શͳϓϩάϥϜͰ͸ͳ͘ɼJDK ͳͲΛҰ෦ղੳର৅֎ͱͯ͠ VTA Λ࣮ߦ͍ͯ͠ΔɽͦͷͨΊɼ‫׬‬શͳϓϩάϥϜΛ࣮‫ݧ‬ର৅ʹͨ͠৔߹ʹ͸ɼࠓճͷ࣮‫݁ݧ‬Ռ͕มΘΔՄೳੑ͕͋Δɽ

antlrant

tomcat

batik

jedit

KS

Torque

2000
1500
1000
500
0

0

0

500

500

1000

1000

1500

1500

2000

2000

An approach for virtual method call resolution with an assumption of a variable typeantlr(a) ԾҾ਺ant

tomcat

batik

jedit

KS

Torqueantlr(b) ϑΟʔϧυ

ant

tomcat

batik

jedit

KS

Torque(c) ϩʔΧϧม਺

antlr

ant

tomcat

batik

jedit

(a) ԾҾ਺KS

Torque

10000
8000
6000
4000
2000
0

0

0

2000

2000

4000

4000

6000

6000

8000

8000

10000

10000

12000

12000

ਤ 4: ϊʔυ‫ݮ‬গྔͷ෼෍

antlr

ant

tomcat

batik

jedit

KS

(b) ϑΟʔϧυ

Torqueantlr

ant

tomcat

batik

jedit

(c) ϩʔΧϧม਺ਤ 5: Τοδ‫ݮ‬গྔͷ෼෍Ծ૝ϝιου‫ͼݺ‬ग़͠ʹ͓͚Δϝιου‫ͼݺ‬ग़͠ީิΛಛఆ͢Δख๏ͱͯ͠ɼϙΠϯλղੳ [7] [8] [9] Λ༻͍Δํ๏΋͋ΔɽFluid Source Code Views ΍ Code Bubbles
Ͱ͸ɼΠϯϥΠϯల։Λߦ͏ࡍʹϝιουΛ‫ͼݺ‬ग़͢ϝιου͕ࣗ໌ʹ‫·ٻ‬Δ͜ͱ
Λར༻͠ɼϙΠϯλղੳͷ͏ͪจ຺Λߟྀͨ͠ղੳΛ༻͍Δ͜ͱͰɼϝιου‫ͼݺ‬ग़͠ީิΛΑΓਖ਼֬ʹ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖ΔՄೳੑ͕͋Δɽ͔͠͠ɼLaurie Β [10] ͷใࠂʹΑΕ͹ɼจ຺Λߟྀͨ͠ϙΠϯλղੳ͸ɼจ຺ඇґଘͳϙΠϯλղੳͱൺ΂ɼϝιου‫ͼݺ‬ग़͠ͷީิ͕͋·Γ‫ݮ‬গ͠ͳ͍͜ͱ͕ใࠂ͞Ε͍ͯΔɽVTA ͸ϑϩʔඇґଘ͔ͭจ຺ඇґଘͳϙΠϯλղੳͱ‫ݪ‬ཧతʹΑ͘ࣅͨख๏Ͱ͋Γɼจ຺Λߟྀͨ͠ख๏Λ༻͍ͯ΋ɼVTA ʹൺ΂ͯਫ਼౓͕େ͖͘޲্͢Δ͜ͱ͸͋·Γͳ͍ͱߟ͑
ΒΕΔɽͦͷͨΊɼຊ࣮‫Ͱݧ‬͸ϙΠϯλղੳͱͷൺֱΛߦΘͳ͔ͬͨɽ

5KSؔ࿈‫ڀݚ‬

͋Δม਺ͷ‫ܕ‬Λࢦఆͨ͠ࡍʹɼͦͷม਺ʹґଘͯ͠‫·ܾ͕ܕ‬Δม਺Λ‫ٻ‬ΊΔผͷํ๏ͱͯ͠ɼΤΠϦΞεղੳ [8] [11] Λ༻͍Δख๏͕ߟ͑ΒΕΔɽΤΠϦΞεղੳͰ͸ɼ͋Δม਺ͱಉ͡ΦϒδΣΫτΛࢀর͢Δม਺Λ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖ΔɽͦͷͨΊ
TPG Λ࢖Θͳ͘ͱ΋ɼΤΠϦΞεղੳʹΑΓࢦఆͨ͠ม਺ͱಉҰͷΦϒδΣΫτΛ
ࢦ͢ม਺ͷू߹ΛಘΔ͜ͱ͕Ͱ͖Δͱߟ͑ΒΕΔɽ
͔͠͠ɼΤΠϦΞεղੳ͸Ұൠʹղੳίετ͕ߴ͘ɼେ‫ن‬໛ͳϓϩάϥϜʹద༻͢Δͷ͸೉͍͠ɽͦͷͨΊɼఏҊख๏Ͱ͸ TPG Λ༻͍Δ͜ͱʹͨ͠ɽ

TorqueFOSE20126·ͱΊͱࠓ‫ޙ‬ͷ՝୊ຊ‫Ͱڀݚ‬͸ɼ஫໨͢Δม਺͕ࢀর͢ΔΦϒδΣΫτͷ‫ܕ‬ΛԾఆͨ͠ঢ়ଶͰͷԾ૝ϝιου‫ͼݺ‬ग़͠ͷղܾख๏ΛఏҊͨ͠ɽ࣮‫Ͱݧ‬͸ɼෳ਺ͷ‫ܕ‬ͷΦϒδΣΫτΛࢀ
র͢Δม਺ɼ‫ܕ‬ΛԾఆͨ͠ͱ͖ʹӨ‫ڹ‬Λड͚ΔՄೳੑͷ͋ΔԾ૝ϝιου‫ͼݺ‬ग़͠ɼͦͯ͠ɼ࣮ࡍʹ‫ܕ‬ΛԾఆͨ͠ͱ͖ͷίʔϧάϥϑͷมԽʹ͍ͭͯௐࠪΛߦͬͨɽ࣮
‫ݧ‬ͷ݁Ռɼෳ਺ͷ‫ܕ‬ΛऔΓ͏ΔΑ͏ͳม਺ࣗମ͸શମʹൺͯ͠গ਺Ͱ͋Δ͕ɼ‫ܕ‬Λ
1 ͭʹ‫ݻ‬ఆͨ͠৔߹ʹίʔϧάϥϑΛେ͖͘‫ݮ‬গͤ͞Δ৔߹͕͋Δ͜ͱΛ֬ೝͨ͠ɽ
ࠓ‫ޙ‬ͷ՝୊ͱͯ͠͸ɼ࣮‫ݧ‬ର৅ͷ‫ن‬໛ͷ֦େ΍ɼ‫ܕ‬Λ‫ݻ‬ఆ͢Δม਺Λ 1 ͭͰ͸ͳ͘ෳ਺ʹͨ͠৔߹ͷίʔϧάϥϑͷมԽͷௐ͕ࠪ‫͛ڍ‬ΒΕΔɽँࣙ ຊ‫ڀݚ‬͸ɼจ෦ՊֶলՊֶ‫ڀݚ‬අิॿۚएख‫( ڀݚ‬A)(՝୊൪߸:23680001) ͷॿ੒Λಘͨɽ
ࢀߟจ‫ݙ‬[ 1 ] Jeﬀrey Dean, David Grove, and Craig Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the 9th European Conference on
Object-Oriented Programming, pp. 77–101, 1995.
[ 2 ] David F. Bacon and Peter F. Sweeney. Fast static analysis of c++ virtual function calls. In
Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming Systems
Languages and Applications, pp. 324–341, 1996.
[ 3 ] Vijay Sundaresan, Laurie Hendren, Chrislain Razaﬁmahefa, Raja Vallée-Rai, Patrick Lam,
Etienne Gagnon, and Charles Godin. Practical virtual method call resolution for java. In Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming, Systems,
Languages, and Applications, pp. 264–280, 2000.
[ 4 ] M. Desmond, M.-A. Storey, and C. Exton. Fluid source code views. In Program Comprehension, 2006. ICPC 2006. 14th IEEE International Conference on, pp. 260 –263, 2006.
[ 5 ] Andrew Bragdon, Steven P. Reiss, Robert Zeleznik, Suman Karumuri, William Cheung,
Joshua Kaplan, Christopher Coleman, Ferdi Adeputra, and Joseph J. LaViola, Jr. Codebubbles: rethinking the user interface paradigm of integrated development environments. In
Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, pp. 455–464, 2010.
[ 6 ] େᆘޫ໌, ѳඒ‫ل‬ण, খྛོࢤ, Ѩ૲ਗ਼࣎. ϝιου‫ڥ‬քΛӽ͑ͨ‫ͼݺ‬ग़͠ύλʔϯநग़ͷͨΊͷίʔϧάϥϑ୳ࡧઓུ. Technical Report 18, ໊‫ݹ‬԰େֶେֶӃ৘ใՊֶ‫ڀݚ‬Պ, 2012.
[ 7 ] Ana Milanova. Light context-sensitive points-to analysis for java. In Proceedings of the
7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pp. 25–30, 2007.
[ 8 ] John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis
using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on
Programming language design and implementation, pp. 131–144, 2004.
[ 9 ] Jianwen Zhu. Symbolic pointer analysis. In Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, pp. 150–157, 2002.
[10] Ondr̆ej Lhoták and Laurie Hendren. Context-sensitive points-to analysis: Is it worth it?
In Compiler Construction, Vol. 3923 of Lecture Notes in Computer Science, pp. 47–64. 2006.
[11] Dacong Yan, Guoqing Xu, and Atanas Rountev. Demand-driven context-sensitive alias
analysis for java. In Proceedings of the 2011 International Symposium on Software Testing andAnalysis, pp. 155–165, 2011.