پیش‌نویس:گراف فراخوانی

"این مقاله در حال ترجمه از ویکی انگلیسی است لطفا حذف نشود."

گراف فراخوانی (که به عنوان مولتی گراف فراخوانی ^[۱] نیز شناخته میشود.) یک گراف کنترل جریان است ، که روابط فراخوانی بین زیر برنامه ها را در یک برنامه کامپیوتری نشان می دهد . هر راس یک دستور العمل را نشان می دهد و هر یال (f, g) نشان می دهد که دستورالعمل f روند g را فراخوانی می کند. در نتیجه، یک چرخه در گراف فراخوانی رویه بازگشتی را نشان می دهد.

مفاهیم پایه ای

گراف های فراخوانی می توانند پویا یا ایستا باشند. ^[۲] یک گراف فراخوانی پویا یک ثبت از اجرای برنامه است، به عنوان مثال به عنوان خروجی توسط یک پروفایلر. بنابراین، یک گراف فراخوانی پویا می تواند دقیق باشد، اما فقط یک بار اجرای برنامه را توصیف می کند. یک گراف فراخوانی ایستا یک گراف فراخوانی است که طراحی شده است تا همه ی اجراهای ممکن برنامه را نمایش دهد. داشتن گراف فراخوانی استاتیک کاملا دقیق یک مساله حل نشدنی است، بنابراین الگوریتم‌های گراف فراخوانی استاتیک معمولاً با تقریب بیش از حد به دست آمده اند. یعنی هر رابطه فراخوانی که رخ می‌دهد در گراف نشان داده می‌شود، و احتمالاً برخی از روابط فراخوانی که هرگز در اجرای واقعی برنامه رخ نمی‌دهند نیز در گراف نمایش داده میشوند.

گرافهای فراخوانی را می توان طوری تعریف کرد که بتوانند درجات مختلفی از دقت را نمایش دهند. یک گراف فراخوانی دقیق تر، رفتار برنامه واقعی را با دقت بیشتری تقریب می کند، به قیمت اینکه زمان بیشتری برای محاسبه کردن و حافظه بیشتری برای ذخیره سازی نیاز داریم. دقیق‌ترین گراف فراخوانی کاملاً به متن حساس است ، به این معنی که گراف برای هر دستور العمل، شامل یک راس جداگانه برای هر پشته فراخوانی است که می‌توان با آن دستور العمل را فعال کرد. یک گراف فراخوانی کاملاً حساس به متن، درخت فراخوانی محتوا نامیده می شود. این را می توان به راحتی به صورت پویا محاسبه کرد، اگرچه ممکن است مقدار زیادی از حافظه را اشغال کند. فراخوانی درخت‌های محتوا معمولاً به صورت ایستا محاسبه نمی‌شود، زیرا ممکن است برای یک برنامه بزرگ خیلی زمان بر باشد. گراف فراخوانی این که کمترین دقت را دارد گراف فراخوانی غیر حساس به متن است ، به این معنی که برای هر رویه فقط یک راس وجود دارد.

با زبان هایی که دارای ارسال پویا هستند ، مانند جاوا و C++ ، محاسبه یک گراف فراخوانی ایستا دقیقاً به نتایج تجزیه و تحلیل مستعار نیاز دارد. ^[۳] و برعکس، محاسبه نام مستعار دقیق به یک گراف فراخوانی نیاز دارد. بسیاری از سیستم های تجزیه و تحلیل استاتیک، رگرسیون نامتناهی ظاهری را با محاسبه آن دو به طور همزمان حل می کنند.

موارد استفاده

گراف های تجزبه را می توان به روش های مختلفی استفاده کرد. یکی از کاربردهای ساده گراف های فراخوانی، یافتن دستورالعمل هایی است که هرگز فراخوانی نمی شوند. گراف های فراخوانی می توانند به عنوان سندی برای درک برنامه ها توسط انسان عمل کنند. ^[۴] آنها همچنین می توانند به عنوان پایه ای برای تجزیه و تحلیل های بیشتر، مانند تجزیه و تحلیلی که جریان مقادیر بین رویه ها را دنبال می کند، یا پیش بینی تأثیر تغییر ، عمل کنند. ^[۵] همچنین از گراف های فراخوانی می توان برای تشخیص ناهنجاری های اجرای برنامه یا حملات تزریق کد استفاده کرد.

نرم افزار

نرم افزارهای رایگان مولد گراف فراخوانی

گراف فراخوانی زمان اجرا (بیشتر ابزارهای فهرست شده پروفایلرهایی با عملکرد گراف فراخوانی هستند)

gprof : در BSD یا بخشی از ابزار باینری گنو گنجانده شده است.
callgrind : بخشی از والگریند(valgrind)
KCachegrind : ابزاری قدرتمند برای تولید و تجزیه و تحلیل گراف های فراخوانی بر اساس داده هایی که توسط callgrind تولید شده اند.
Mac OS X Activity Monitor: مانیتور فرایند رابط کاربر گرافیکی اپل دارای یک تولید کننده ی گراف فراخوانی درون خود است که می تواند فرایندهارا به صورت نمونه تولید کند و یک گراف فراخوانی برگرداند. این عملکرد فقط در Mac OS X Leopard موجود است.
OpenPAT : شامل ابزار کنترل جریان است که به طور خودکار یک تصویر گراف فراخوانی Graphviz را از اندازه گیری های زمان اجرای برنامه ایجاد می‌کند.
pprof ، ابزار منبع باز برای تجسم و تجزیه و تحلیل داده های پروفایل است، تا در ارتباط با gperftools استفاده شود .
CodeAnalyst از AMD (منتشر شده تحت GPL)
makeppgraph یک مولد گراف وابستگی (در سطح ماژول) برای ساخته های عملی شده با makepp است .
Intel(R) Single Event API (رایگان، منبع باز)

استاتیک برای دریافت گراف فراخوانی بدون اجرای برنامه

Go

برو-کالویس : یک مولد گراف فراخوانی تعاملی برای برنامه های Go است که خروجی آن را می توان با Graphviz ترسیم کرد.

چند زبانه

callGraph : مولد گراف فراخوانی منبع باز برای awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl, and typescript.

.NET

NDepend :یک ابزار تحلیل ایستا برای کد NET. است این ابزار از تعداد زیادی معیار کد پشتیبانی می کند و امکان تجسم وابستگی ها را با استفاده از گراف های جهت دار و ماتریس وابستگی فراهم می کند.

PHP، Perl و Python

توسعه دهنده::NYTProf : یک تحلیلگر عملکرد پرل و مولد نمودار فراخوانی است.
phpCallGraph : یک مولد گراف فراخوانی برای برنامه های PHP که از Graphviz استفاده می کند. به زبان PHP نوشته شده است و حداقل به PHP 5.2 نیاز دارد.
pycallgraph : یک مولد گراف فراخوانی برای برنامه های پایتون است که از Graphviz استفاده می کند.
پیان : یک مولد گراف فراخوانی ایستا برای برنامه های پایتون که از Graphviz استفاده می کند.
gprof2dot : یک مولد گراف فراخوانی که به زبان پایتون نوشته شده است که داده‌های پروفایل برای بسیاری از زبان‌ها/زمان‌های اجرا را به یک Graphviz callgraph تبدیل می‌کند.
code2flow : یک مولد گراف فراخوانی برای برنامه های پایتون و جاوا اسکریپت که از Graphviz استفاده می کند
rcviz : ماژول پایتون برای رندر کردن گراف های تماس تولید شده در زمان اجرا با Graphviz . هر راس نشان دهنده فراخوانی یک تابع با پارامترهای ارسال شده به آن و مقداری که بازگشته است.

XQuery

نمودارهای فراخوانی XQuery از ویکی‌بوک XQuery : یک مولد گراف فراخوانی برای یک ماژول تابع XQuery که از Graphviz استفاده می‌کند

مولد گراف فراخوانی اختصاصی

بستر آزمایش LDRA: موتورهای تجزیه و تحلیل استاتیک و پویا برای هر دو نرم افزار میزبان و هم جاسازی شده، با تعداد بی شماری از گزارش ها از جمله گراف فراخوانی.
تحلیلگر پروژه: تحلیلگر کد ایستا و مولد گراف فراخوانی برای کدهای ویژوال بیسیک
کارشناس بصری: تحلیلگر کد ایستا و مولد گراف فراخوانی برای Oracle PL/SQL ، SQLServer Transact-SQL ، C# و کد PowerBuilder
آنالایزر عملکرد اینتل VTune: نمایه ساز ابزار دقیق برای نمایش گراف فراخوانی و آمار اجرای برنامه
مجموعه ابزار مهندسی مجدد نرم افزار DMS: ابزار تجزیه و تحلیل برنامه قابل تنظیم با استخراج گراف فراخوانی سراسری استاتیک کل برنامه برای C، جاوا و COBOL

سایر ابزارهای مرتبط

<a href="https://en.wikipedia.org/wiki/Graphviz" rel="mw:ExtLink" title="Graphviz" class="cx-link" data-linkid="146">Graphviz</a>: یک نمایش متنی از هر گراف (از جمله گراف فراخوانی) را به تصویر تبدیل می کند.
<a href="https://en.wikipedia.org/wiki/Tsort" rel="mw:ExtLink" title="Tsort" class="cx-link" data-linkid="149">tsort</a>: ابزار خط فرمان که مرتب‌سازی توپولوژیکی را انجام می‌دهد.

↑ Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K. (April 1990). "Constructing the procedure call multigraph". IEEE Transactions on Software Engineering. 16 (4): 483–487. doi:10.1109/32.54302.
↑ Ryder, B.G. (May 1979). "Constructing the Call Graph of a Program". IEEE Transactions on Software Engineering. SE-5 (3): 216–226. doi:10.1109/tse.1979.234183.
↑ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 October 1997). "Call graph construction in object-oriented languages". ACM SIGPLAN Notices. ACM. 32 (10): 108, 108–124, 124. doi:10.1145/263700.264352.
↑ Eisenbarth, T.; Koschke, R.; Simon, D. (2001). "Aiding program comprehension by static and dynamic feature analysis". Proceedings IEEE International Conference on Software Maintenance. ICSM 2001: 602–611. doi:10.1109/icsm.2001.972777. ISBN 0-7695-1189-9.
↑ Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (26 July 2016). "A large-scale study of call graph-based impact prediction using mutation testing". Software Quality Journal. 25 (3): 921–950. arXiv:1812.06286. doi:10.1007/s11219-016-9332-8.

[1] Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K. (April 1990). "Constructing the procedure call multigraph". IEEE Transactions on Software Engineering. 16 (4): 483–487. doi:10.1109/32.54302.

[2] Ryder, B.G. (May 1979). "Constructing the Call Graph of a Program". IEEE Transactions on Software Engineering. SE-5 (3): 216–226. doi:10.1109/tse.1979.234183.

[3] Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 October 1997). "Call graph construction in object-oriented languages". ACM SIGPLAN Notices. ACM. 32 (10): 108, 108–124, 124. doi:10.1145/263700.264352.

[4] Eisenbarth, T.; Koschke, R.; Simon, D. (2001). "Aiding program comprehension by static and dynamic feature analysis". Proceedings IEEE International Conference on Software Maintenance. ICSM 2001: 602–611. doi:10.1109/icsm.2001.972777. ISBN 0-7695-1189-9.

[5] Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (26 July 2016). "A large-scale study of call graph-based impact prediction using mutation testing". Software Quality Journal. 25 (3): 921–950. arXiv:1812.06286. doi:10.1007/s11219-016-9332-8.

[۱]

[۲]

[۳]

[۴]

[۵]