Ada 95 Quality and Style Guide | Chapter 5 |
5.6.6 Recursion and Iteration Boundsguideline
Consider specifying bounds on loops .
Consider specifying bounds on recursion . example
Establishing an iteration bound:
Safety_Counter := 0; Process_List: loop exit when Current_Item = null; ... Current_Item := Current_Item.Next; ... Safety_Counter := Safety_Counter + 1; if Safety_Counter > 1_000_000 then raise Safety_Error; end if; end loop Process_List;Establishing a recursion bound:
subtype Recursion_Bound is Natural range 0 .. 1_000; procedure Depth_First (Root : in Tree; Safety_Counter : in Recursion_Bound := Recursion_Bound'Last) is begin if Root /= null then if Safety_Counter = 0 then raise Recursion_Error; end if; Depth_First (Root => Root.Left_Branch, Safety_Counter => Safety_Counter - 1); Depth_First (Root => Root.Right_Branch, Safety_Counter => Safety_Counter - 1); ... -- normal subprogram body end if; end Depth_First;Following are examples of this subprogram's usage. One call specifies a maximum recursion depth of 50. The second takes the default (1,000). The third uses a computed bound:
Depth_First(Root => Tree_1, Safety_Counter => 50); Depth_First(Tree_2); Depth_First(Root => Tree_3, Safety_Counter => Current_Tree_Height);rationale
Recursion, and iteration using structures other than for statements, can be infinite because the expected terminating condition does not arise. Such faults are sometimes quite subtle, may occur rarely, and may be difficult to detect because an external manifestation might be absent or substantially delayed.
By including counters and checks on the counter values, in addition to the loops themselves, you can prevent many forms of infinite loops. The inclusion of such checks is one aspect of the technique called Safe Programming (Anderson and Witty 1978).
The bounds of these checks do not have to be exact, just realistic. Such counters and checks are not part of the primary control structure of the program but a benign addition functioning as an execution-time "safety net," allowing error detection and possibly recovery from potential infinite loops or infinite recursion.
notes
If a loop uses the for iteration scheme (Guideline 5.6.4), it follows this guideline.
exceptions
Embedded control applications have loops that are intended to be infinite. Only a few loops within such applications should qualify as exceptions to this guideline. The exceptions should be deliberate (and documented ) policy decisions.
This guideline is most important to safety critical systems. For other systems, it may be overkill.
< Previous Page | Search | Contents | Index | Next Page > |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
TOC | TOC | TOC | TOC | TOC | TOC | TOC | TOC | TOC | TOC | TOC |
Appendix | References | Bibliography |