ในการวิเคราะห์โปรแกรมการวิเคราะห์รูปร่าง ( Shape Analysis ) เป็น เทคนิค การวิเคราะห์โค้ดแบบคงที่ (Static Code Analysis)ที่ใช้ค้นหาและตรวจสอบคุณสมบัติของโครงสร้างข้อมูลที่เชื่อมโยงกันและจัดสรรหน่วยความจำแบบไดนามิก ในโปรแกรมคอมพิวเตอร์ (โดยทั่วไปจะ เป็นแบบเชิงคำ สั่ง ) โดยทั่วไปจะใช้ในระหว่างการคอมไพล์เพื่อค้นหาข้อบกพร่องของซอฟต์แวร์หรือเพื่อตรวจสอบคุณสมบัติความถูกต้องระดับสูงของโปรแกรม ใน โปรแกรม Javaสามารถใช้เพื่อตรวจสอบให้แน่ใจว่าเมธอด sort เรียงลำดับรายการได้อย่างถูกต้อง สำหรับ โปรแกรม Cอาจใช้เพื่อค้นหาตำแหน่งที่บล็อกหน่วยความจำไม่ได้ถูกปล่อยอย่างถูกต้อง

การวิเคราะห์รูปทรงถูกนำไปประยุกต์ใช้กับปัญหาต่างๆ มากมาย:

• ความปลอดภัยของหน่วยความจำ: การค้นหาการรั่วไหลของหน่วยความจำการอ้างอิงของพอยเตอร์ที่ค้างอยู่และการค้นพบกรณีที่บล็อกหน่วยความจำถูกปล่อยมากกว่าหนึ่งครั้ง^{[ 1 ] [ 2 ]}
• การค้นหาข้อผิดพลาดเกี่ยวกับขอบเขตของอาร์เรย์
• การตรวจสอบคุณสมบัติสถานะประเภท (ตัวอย่างเช่น การตรวจสอบให้แน่ใจว่าไฟล์นั้นเป็นประเภทopen()ที่ถูกต้องก่อนที่จะเป็นประเภทที่ถูกต้องread())
• การตรวจสอบให้แน่ใจว่าวิธีการย้อนกลับรายการเชื่อมโยงจะไม่ทำให้เกิดวงจรในรายการ^{[ 2 ]}

การวิเคราะห์รูปร่างเป็นรูปแบบหนึ่งของการวิเคราะห์ตัวชี้แม้ว่าจะมีความแม่นยำมากกว่าการวิเคราะห์ตัวชี้แบบทั่วไปก็ตาม การวิเคราะห์ตัวชี้พยายามกำหนดชุดของวัตถุที่ตัวชี้สามารถชี้ไปได้ (เรียกว่าชุดจุดที่ตัวชี้ชี้ไป) น่าเสียดายที่การวิเคราะห์เหล่านี้จำเป็นต้องเป็นการประมาณ (เนื่องจากการวิเคราะห์แบบคงที่ที่แม่นยำอย่างสมบูรณ์แบบสามารถแก้ปัญหาการหยุดทำงานได้ ) การวิเคราะห์รูปร่างสามารถกำหนดชุดจุดที่เล็กกว่า (แม่นยำกว่า) ได้

ลองพิจารณา โปรแกรม C++อย่างง่ายต่อไปนี้

รายการ* รายการ[ 10 ];for ( int i = 0 ; i < 10 ; ++ i ) { items [ i ] = new Item (...); // บรรทัด [1] }process_items ( items ); // บรรทัด [2]for ( int i = 0 ; i < 10 ; ++ i ) { delete items [ i ]; // บรรทัด [3] }

โปรแกรมนี้สร้างอาร์เรย์ของวัตถุ ประมวลผลวัตถุเหล่านั้นด้วยวิธีใดวิธีหนึ่ง และจากนั้นลบวัตถุเหล่านั้น สมมติว่าprocess_itemsฟังก์ชันนี้ปราศจากข้อผิดพลาด โปรแกรมนี้จึงปลอดภัยอย่างเห็นได้ชัด เพราะมันจะไม่เรียกใช้หน่วยความจำที่ถูกปล่อยไปแล้ว และมันจะลบวัตถุทั้งหมดที่มันสร้างขึ้น

น่าเสียดายที่การวิเคราะห์พอยเตอร์ส่วนใหญ่ไม่สามารถวิเคราะห์โปรแกรมนี้ได้อย่างแม่นยำ เพื่อที่จะระบุเซตของพอยเตอร์ที่ชี้ไป การวิเคราะห์พอยเตอร์ต้องสามารถตั้งชื่ออ็อบเจ็กต์ของโปรแกรมได้ โดยทั่วไป โปรแกรมสามารถจัดสรรอ็อบเจ็กต์ได้ไม่จำกัดจำนวน แต่เพื่อที่จะสิ้นสุดการทำงาน การวิเคราะห์พอยเตอร์สามารถใช้ได้เพียงชุดชื่อที่จำกัดเท่านั้น วิธีการประมาณค่าทั่วไปคือการตั้งชื่อเดียวกันให้กับอ็อบเจ็กต์ทั้งหมดที่จัดสรรในบรรทัดใดบรรทัดหนึ่งของโปรแกรม ในตัวอย่างข้างต้น อ็อบเจ็กต์ทั้งหมดที่สร้างขึ้นในบรรทัด [1] จะมีชื่อเดียวกัน ดังนั้น เมื่อdeleteวิเคราะห์คำสั่งเป็นครั้งแรก การวิเคราะห์จะพบว่าอ็อบเจ็กต์หนึ่งที่มีชื่อ [1] กำลังถูกลบ ในครั้งที่สองที่วิเคราะห์คำสั่ง (เนื่องจากอยู่ในลูป) การวิเคราะห์จะเตือนถึงข้อผิดพลาดที่อาจเกิดขึ้น เนื่องจากไม่สามารถแยกแยะอ็อบเจ็กต์ในอาร์เรย์ได้ จึงอาจเป็นไปได้ว่าครั้งที่สองdeleteกำลังลบอ็อบเจ็กต์เดียวกันกับครั้งแรกdeleteคำเตือนนี้ไม่ถูกต้อง และเป้าหมายของการวิเคราะห์รูปร่างคือการหลีกเลี่ยงคำเตือนดังกล่าว

การวิเคราะห์รูปร่างช่วยแก้ปัญหาของการวิเคราะห์ตัวชี้โดยใช้ระบบการตั้งชื่อวัตถุที่มีความยืดหยุ่นมากกว่า แทนที่จะตั้งชื่อวัตถุเดียวกันตลอดทั้งโปรแกรม วัตถุสามารถเปลี่ยนชื่อได้ขึ้นอยู่กับการกระทำของโปรแกรม บางครั้ง วัตถุที่แตกต่างกันหลายชิ้นที่มีชื่อต่างกันอาจถูกสรุปหรือรวมเข้าด้วยกันเพื่อให้มีชื่อเดียวกัน จากนั้น เมื่อโปรแกรมกำลังจะใช้วัตถุที่ถูกสรุปนั้น ก็สามารถทำให้เป็นรูปธรรมได้กล่าวคือ วัตถุที่ถูกสรุปจะถูกแบ่งออกเป็นสองวัตถุที่มีชื่อต่างกัน โดยวัตถุหนึ่งแทนวัตถุชิ้นเดียว และอีกวัตถุหนึ่งแทนวัตถุที่ถูกสรุปที่เหลืออยู่ หลักการพื้นฐานของการวิเคราะห์รูปร่างคือ วัตถุที่โปรแกรมกำลังใช้งานจะถูกแทนด้วยวัตถุที่เป็นรูปธรรมที่ไม่ซ้ำกัน ในขณะที่วัตถุที่ไม่ได้ใช้งานจะถูกสรุป

อาร์เรย์ของวัตถุในตัวอย่างข้างต้นได้รับการสรุปในรูปแบบต่างๆ ที่บรรทัด [1], [2] และ [3] ที่บรรทัด [1] อาร์เรย์ถูกสร้างขึ้นเพียงบางส่วนเท่านั้น องค์ประกอบอาร์เรย์ 0..i-1 ประกอบด้วยวัตถุที่สร้างขึ้น องค์ประกอบอาร์เรย์ i กำลังจะถูกสร้างขึ้น และองค์ประกอบถัดไปยังไม่ได้เริ่มต้น การวิเคราะห์รูปร่างสามารถประมาณสถานการณ์นี้ได้โดยใช้การสรุปสำหรับชุดองค์ประกอบแรก ตำแหน่งหน่วยความจำที่สร้างขึ้นสำหรับองค์ประกอบ i และการสรุปสำหรับตำแหน่งที่ยังไม่ได้เริ่มต้นที่เหลือ ดังนี้:

หลังจากลูปสิ้นสุดลงที่บรรทัด [2] ไม่จำเป็นต้องเก็บสิ่งใดไว้ การวิเคราะห์รูปร่างจะกำหนด ณ จุดนี้ว่าองค์ประกอบอาร์เรย์ทั้งหมดได้รับการเริ่มต้นแล้ว:

อย่างไรก็ตาม ที่บรรทัด [3] องค์ประกอบของอาร์เรย์iถูกใช้งานอีกครั้ง ดังนั้น การวิเคราะห์จึงแบ่งอาร์เรย์ออกเป็นสามส่วนเช่นเดียวกับในบรรทัด [1] แต่ในครั้งนี้ ส่วนแรกก่อนหน้านั้นiถูกลบไปแล้ว และองค์ประกอบที่เหลือยังคงถูกต้อง (โดยสมมติว่าdeleteคำสั่งยังไม่ได้ดำเนินการ)

โปรดสังเกตว่าในกรณีนี้ การวิเคราะห์รับรู้ว่าตัวชี้ที่ดัชนีiยังไม่ถูกลบ ดังนั้นจึงไม่แจ้งเตือนเกี่ยวกับการลบซ้ำซ้อน

• การวิเคราะห์นามแฝง
• การวิเคราะห์การหลบหนี

• Neil D. Jones; Steven S. Muchnick (1982). "แนวทางที่ยืดหยุ่นสำหรับการวิเคราะห์การไหลของข้อมูลระหว่างกระบวนการและการเขียนโปรแกรมที่มีโครงสร้างข้อมูลแบบเรียกซ้ำ". รายงานการประชุมสัมมนา ACM SIGPLAN-SIGACT ครั้งที่ 9 เรื่องหลักการของภาษาการเขียนโปรแกรม - POPL '82 . ACM. หน้า  66–74 . doi : 10.1145/582153.582161 . ISBN 0897910656. S2CID  13266723 .

• Mooly Sagiv ; Thomas Reps ; Reinhard Wilhelm (พฤษภาคม 2002). "การวิเคราะห์รูปร่างพาราเมตริกผ่านตรรกะ 3 ค่า" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 24 (3). ACM: 217– 298. CiteSeerX  10.1.1.147.2132 . doi : 10.1145/292540.292552 . S2CID  101653 .

• Wilhelm, Reinhard; Sagiv, Mooly; Reps, Thomas (2007). "บทที่ 12: การวิเคราะห์รูปร่างและการประยุกต์ใช้". ใน Srikant, YN; Shankar, Priti (บรรณาธิการ). คู่มือการออกแบบคอมไพเลอร์: การเพิ่มประสิทธิภาพและการสร้างรหัสเครื่อง ฉบับที่สอง . สำนักพิมพ์ CRC. หน้า 12–1–12–44. ISBN 978-1-4200-4382-2.