تعقيد الحلقات

توجد طرق متعددة لتعريف التعقيد الحلقي لجزء من شفرة المصدر . إحدى الطرق الشائعة هي عدد المسارات المستقلة خطيًا داخله. مجموعة${\displaystyle S}$تكون مجموعة المسارات مستقلة خطيًا إذا كانت مجموعة حواف أي مسار${\displaystyle P}$في${\displaystyle S}$لا يمثل اتحاد مجموعات حواف المسارات في مجموعة فرعية من${\displaystyle S/P}$إذا لم يحتوي الكود المصدري على أي عبارات تحكم في التدفق (شروط أو نقاط قرار)، فسيكون التعقيد 1، لوجود مسار واحد فقط عبر الكود. أما إذا احتوى الكود على عبارة IF واحدة بشرط واحد ، فسيكون هناك مساران: أحدهما عندما تكون عبارة IF صحيحة، والآخر عندما تكون خاطئة. في هذه الحالة، سيكون التعقيد 2. أما عبارتا IF متداخلتان بشرط واحد، أو عبارة IF واحدة بشرطين، فستكون التعقيد 3.

هناك طريقة أخرى لتعريف التعقيد الحلقي لبرنامج ما، وهي النظر إلى مخطط تدفق التحكم الخاص به ، وهو مخطط موجه يحتوي على الكتل الأساسية للبرنامج، مع وجود حافة بين كتلتين أساسيتين إذا كان من الممكن أن ينتقل التحكم من الأولى إلى الثانية. ويُعرَّف التعقيد M حينها على النحو التالي ^{[ 2 ].}

$${\displaystyle M=E-N+2P,}$$

أين

• E = عدد حواف الرسم البياني.
• N = عدد عقد الرسم البياني.
• P = عدد المكونات المتصلة .

يتمثل أحد البدائل المقترحة أصلاً في استخدام رسم بياني تكون فيه كل نقطة خروج متصلة بنقطة الدخول. في هذه الحالة، يكون الرسم البياني متصلاً بقوة . هنا، يساوي التعقيد الحلقي للبرنامج العدد الحلقي لرسمه البياني (المعروف أيضاً باسم عدد بيتي الأول )، والذي يُعرَّف على النحو التالي ^{[ 2 ].}$${\displaystyle M=E-N+P.}$$

يمكن اعتبار ذلك بمثابة حساب عدد الدورات المستقلة خطيًا الموجودة في الرسم البياني: أي تلك الدورات التي لا تحتوي على دورات أخرى داخلها. ولأن كل نقطة خروج تعود إلى نقطة الدخول، فهناك دورة واحدة على الأقل من هذا النوع لكل نقطة خروج.

بالنسبة لبرنامج واحد (أو روتين فرعي أو طريقة)، فإن P تساوي دائمًا 1؛ صيغة أبسط لروتين فرعي واحد هي ^{[ 3 ]}$${\displaystyle M=E-N+2.}$$

يمكن تطبيق التعقيد الحلقي على عدة برامج أو برامج فرعية في آن واحد (على جميع الدوال في فئة معينة، على سبيل المثال). في هذه الحالات، يساوي P عدد البرامج المعنية، ويظهر كل برنامج فرعي كمجموعة فرعية منفصلة من الرسم البياني.

أظهر مكابي أن التعقيد الحلقي لبرنامج منظم ذي نقطة دخول واحدة ونقطة خروج واحدة يساوي عدد نقاط القرار (عبارات if أو الحلقات الشرطية) الموجودة في ذلك البرنامج زائد واحد. هذا صحيح فقط بالنسبة لنقاط القرار المحسوبة على مستوى تعليمات الآلة. ^{[ 4 ]} أما القرارات التي تتضمن مسندات مركبة، كتلك الموجودة في لغات البرمجة عالية المستوى ، IF cond1 AND cond2 THEN ...فينبغي حسابها بدلالة متغيرات المسندات المستخدمة. في هذا المثال، ينبغي حساب نقطتي قرار، لأنه على مستوى الآلة يُعادل ذلك IF cond1 THEN IF cond2 THEN .... ^{[ 2 ] [ 5 ]}

يمكن توسيع مفهوم التعقيد الحلقي ليشمل برنامجًا ذا نقاط خروج متعددة. في هذه الحالة، يكون مساويًا لـ $${\displaystyle \pi -s+2,}$$ أين${\displaystyle \pi }$يمثل عدد نقاط اتخاذ القرار في البرنامج، ويمثل عدد نقاط الخروج. ^{[ 5 ] [ 6 ]}

في عرضه التقديمي بعنوان " مقاييس جودة البرمجيات لتحديد المخاطر" ^{[ 7 ]} لوزارة الأمن الداخلي، قدم توم مكابي التصنيف التالي للتعقيد الحلقي:

• 1-10: إجراء بسيط، مخاطر قليلة
• 11-20: أكثر تعقيدًا، خطر متوسط
• 21-50: معقد، عالي الخطورة
• > 50: كود غير قابل للاختبار، مخاطرة عالية جدًا

كان أحد تطبيقات مكابي الأصلية هو الحد من تعقيد الإجراءات أثناء تطوير البرامج. أوصى مكابي المبرمجين بحساب تعقيد الوحدات التي يطورونها، وتقسيمها إلى وحدات أصغر كلما تجاوز التعقيد الحلقي للوحدة 10. ^{[ 2 ]} وقد تبنت منهجية الاختبار الهيكلي للمعهد الوطني للمعايير والتكنولوجيا (NIST) هذه الممارسة ، حيث لاحظت أنه منذ نشر مكابي الأصلي، حظي الرقم 10 بأدلة داعمة كبيرة. ومع ذلك، أشارت المنهجية أيضًا إلى أنه في بعض الحالات، قد يكون من المناسب تخفيف هذا القيد والسماح بوحدات ذات تعقيد يصل إلى 15. ولأن المنهجية أقرت بوجود أسباب عرضية لتجاوز الحد المتفق عليه، فقد صاغت توصيتها على النحو التالي: "لكل وحدة، إما أن تحدد التعقيد الحلقي عند [الحد المتفق عليه] أو تقدم شرحًا كتابيًا لسبب تجاوز هذا الحد." ^{[ 9 ]}

يتناول القسم السادس من ورقة مكابي البحثية لعام 1976 تحديد شكل مخططات تدفق التحكم (CFGs) للبرامج غير المهيكلة من حيث مخططاتها الفرعية، والتي حددها مكابي. (للمزيد من التفاصيل، انظر نظرية البرنامج المهيكل ). واختتم مكابي ذلك القسم باقتراح مقياس عددي لمدى قرب برنامج معين من نموذج البرمجة المهيكلة المثالي، أي "هيكليته". أطلق مكابي على المقياس الذي ابتكره لهذا الغرض اسم التعقيد الأساسي . ^{[ 2 ]}

لحساب هذا المقياس، يتم اختزال مخطط التدفق الحر الأصلي بشكل تكراري من خلال تحديد المخططات الفرعية التي تحتوي على نقطة دخول واحدة ونقطة خروج واحدة، ثم استبدالها بعقدة واحدة. يتوافق هذا الاختزال مع ما يفعله الإنسان عند استخراج روتين فرعي من جزء أكبر من التعليمات البرمجية. (يُصنف هذا الإجراء حاليًا ضمن مصطلح إعادة هيكلة التعليمات البرمجية ). سُميت طريقة اختزال مكابي لاحقًا بالتكثيف في بعض الكتب الدراسية، لأنها اعتُبرت تعميمًا للتكثيف على المكونات المستخدمة في نظرية المخططات . ^{[ 10 ]} إذا كان البرنامج مُهيكلًا، فإن عملية اختزال/تكثيف مكابي تُختزله إلى عقدة واحدة في مخطط التدفق الحر. في المقابل، إذا لم يكن البرنامج مُهيكلًا، فإن العملية التكرارية ستحدد الجزء غير القابل للاختزال. مقياس التعقيد الأساسي الذي حدده مكابي هو ببساطة التعقيد الحلقي لهذا المخطط غير القابل للاختزال، لذا سيكون مساويًا لـ 1 لجميع البرامج المُهيكلة، ولكنه أكبر من 1 للبرامج غير المُهيكلة. ^{[ 9 ] : 80}

يتمثل تطبيق آخر للتعقيد الحلقي في تحديد عدد حالات الاختبار اللازمة لتحقيق تغطية اختبار شاملة لوحدة معينة.

وهو مفيد بسبب خاصيتين للتعقيد الحلقي، M ، لوحدة نمطية محددة:

• M هو الحد الأعلى لعدد حالات الاختبار اللازمة لتحقيق تغطية كاملة للفروع .
• يمثل M الحد الأدنى لعدد المسارات عبر مخطط تدفق التحكم (CFG). بافتراض أن كل حالة اختبار تسلك مسارًا واحدًا، فإن عدد الحالات اللازمة لتغطية المسارات يساوي عدد المسارات الممكنة فعليًا. ولكن قد تكون بعض المسارات مستحيلة، لذا على الرغم من أن عدد المسارات عبر مخطط تدفق التحكم يمثل بوضوح الحد الأعلى لعدد حالات الاختبار اللازمة لتغطية المسارات، فإن هذا العدد الأخير ( للمسارات الممكنة ) يكون أحيانًا أقل من M.

قد تتساوى الأرقام الثلاثة المذكورة أعلاه: تغطية الفروع${\displaystyle \leq }$التعقيد الحلقي${\displaystyle \leq }$عدد المسارات.

على سبيل المثال، لنفترض برنامجًا يتكون من عبارتين متتاليتين من نوع if-then-else.

إذا كان ( c1 ()) f1 ()؛ وإلا f2 ()؛إذا كان ( c2 ()) f3 ()؛ وإلا f4 ()؛

في هذا المثال، تكفي حالتا اختبار لتحقيق تغطية كاملة للفروع، بينما يلزم أربع حالات لتغطية كاملة للمسارات. التعقيد الحلقي للبرنامج هو 3 (حيث يحتوي الرسم البياني المتصل بقوة للبرنامج على 8 حواف، و7 عقد، ومكون متصل واحد) ( 8 - 7 + 2 ).

بشكل عام، لاختبار وحدة برمجية بشكل كامل، يجب اختبار جميع مسارات التنفيذ فيها. وهذا يعني أن الوحدة ذات رقم التعقيد العالي تتطلب جهدًا أكبر في الاختبار مقارنةً بالوحدة ذات الرقم المنخفض، لأن رقم التعقيد الأعلى يشير إلى مسارات أكثر في الكود. كما يعني هذا أيضًا أن الوحدة ذات التعقيد العالي أصعب فهمًا، إذ يجب على المبرمج فهم المسارات المختلفة ونتائجها. ^{[ 11 ]} لا يغطي التعقيد الحلقي سوى جانب واحد من جوانب البرمجيات، لذا فإن الاعتماد عليه وحده قد لا يوفر تمثيلًا كاملًا للتعقيد الكلي للبرنامج.

لسوء الحظ، ليس من العملي دائمًا اختبار جميع المسارات الممكنة في البرنامج. بالنظر إلى المثال أعلاه، في كل مرة تُضاف فيها عبارة شرطية (if-then-else)، يتضاعف عدد المسارات الممكنة. ومع نمو البرنامج بهذه الطريقة، سرعان ما يصل إلى نقطة يصبح فيها اختبار جميع المسارات غير عملي.

تتمثل إحدى استراتيجيات الاختبار الشائعة، التي تتبناها على سبيل المثال منهجية الاختبار الهيكلي الصادرة عن المعهد الوطني للمعايير والتكنولوجيا (NIST)، في استخدام التعقيد الحلقي للوحدة البرمجية لتحديد عدد اختبارات الصندوق الأبيض اللازمة لتغطية الوحدة بشكل كافٍ. في معظم الحالات، ووفقًا لهذه المنهجية، ينبغي أن تحتوي الوحدة البرمجية على عدد من الاختبارات لا يقل عن تعقيدها الحلقي. وفي أغلب الأحيان، يكون هذا العدد من الاختبارات كافيًا لتغطية جميع المسارات ذات الصلة بالوظيفة. ^{[ 9 ]}

كمثال على دالة تتطلب أكثر من مجرد تغطية الفروع لاختبارها بدقة، أعد النظر في الدالة المذكورة أعلاه. مع ذلك، افترض أنه لتجنب حدوث خطأ، يجب على أي كود يستدعي إحدى الدالتين `and` f1()أو `or` f3()أن يستدعي الأخرى أيضًا. ^{[ أ ]} بافتراض أن نتائج ` c1()and` و` c2()or` مستقلة، فإن الدالة كما هي معروضة أعلاه تحتوي على خطأ. تسمح تغطية الفروع باختبار الدالة باختبارين فقط، مثل حالات الاختبار التالية:

• c1()تُرجع القيمة "صحيح" c2()وتُرجع القيمة "صحيح".
• c1()يُرجع خطأً c2()ويُرجع خطأً

لا تكشف أي من هاتين الحالتين عن الخلل. ولكن إذا استخدمنا التعقيد الحلقي للإشارة إلى عدد الاختبارات المطلوبة، فإن العدد يرتفع إلى 3. لذا، يجب علينا اختبار أحد المسارات التالية:

• c1()تُرجع القيمة true وتُرجع c2()القيمة false
• c1()تُرجع القيمة خطأ وتُرجع c2()القيمة صحيح

أي من هذين الاختبارين سيكشف عن الخلل.

أجرت دراسات عديدة بحثًا في العلاقة بين رقم التعقيد الحلقي لماكابي وتكرار حدوث العيوب في دالة أو طريقة. ^{[ 12 ]} وجدت بعض الدراسات ^{[ 13 ]} ارتباطًا إيجابيًا بين التعقيد الحلقي والعيوب؛ فالدوال والطرق ذات التعقيد الأعلى تميل أيضًا إلى احتواء أكبر عدد من العيوب. مع ذلك، فقد ثبت مرارًا وتكرارًا وجود ارتباط بين التعقيد الحلقي وحجم البرنامج (الذي يُقاس عادةً بعدد أسطر التعليمات البرمجية ). ^{[ 14 ]} زعم ليس هاتون ^{[ 15 ]} أن للتعقيد نفس القدرة التنبؤية لعدد أسطر التعليمات البرمجية. أما الدراسات التي راعت حجم البرنامج (أي مقارنة الوحدات ذات التعقيدات المختلفة ولكن الأحجام المتشابهة) فهي عمومًا أقل حسمًا، إذ لم يجد الكثير منها أي ارتباط ذي دلالة إحصائية، بينما وجد البعض الآخر ارتباطًا. يشكك بعض الباحثين في صحة الأساليب المستخدمة في الدراسات التي لم تجد ارتباطًا. ^{[ 16 ]} على الرغم من أن هذه العلاقة موجودة على الأرجح، إلا أنه ليس من السهل استخدامها عمليًا. ^{[ 17 ]} بما أن حجم البرنامج ليس سمة قابلة للتحكم في البرامج التجارية ، فقد تم التشكيك في جدوى رقم مكابي. ^{[ 12 ]} جوهر هذه الملاحظة هو أن البرامج الأكبر حجمًا تميل إلى أن تكون أكثر تعقيدًا وتحتوي على المزيد من العيوب. لم يثبت أن تقليل التعقيد الحلقي للشيفرة يقلل من عدد الأخطاء أو العيوب فيها. ومع ذلك، فإن معايير السلامة الدولية مثل ISO 26262 تفرض إرشادات برمجة توصي بمراقبة تعقيد الشيفرة والسعي إلى تقليله، وعندما يكون التعقيد مرتفعًا ، يُتوقع اتخاذ تدابير إضافية تشمل التدقيق في أنشطة التحقق والتدقيق الأكثر صعوبة، بما في ذلك الاختبار. ^{[ 18 ]}