Coding Guidelines and Undecidability

The C and C++ programming languages are widely used for the implementation of software in critical systems. They are complex languages with subtle features and peculiarities that might baffle even the more expert programmers. Hence, the general prescription of language subsetting, which occurs in most functional safety standards and amounts to only using a "safer" subset of the language, is particularly applicable to them. Coding guidelines are the preferred way of expressing language subsets. Some guidelines are formulated in terms of the programming language and its implementation only: in this case they are amenable to automatic checking. However, due to fundamental limitations of computing, some guidelines are undecidable, that is, they are based on program properties that no current and future algorithm can capture in all cases. The most mature and widespread coding standards, the MISRA ones, explicitly tag guidelines with undecidable or decidable. It turns out that this information is not of secondary nature and must be taken into account for a full understanding of what the guideline is asking for. As a matter of fact, undecidability is a common source of confusion affecting many users of coding standards and of the associated checking tools. In this paper, we recall the notions of decidability and undecidability in terms that are understandable to any C/C++ programmer. The paper includes a systematic study of all the undecidable MISRA C:2012 guidelines, discussing the reasons for the undecidability and its consequences. We pay particular attention to undecidable guidelines that have decidable approximations whose enforcement would not overly constrain the source code. We also discuss some coding guidelines for which compliance is hard, if not impossible, to prove, even beyond the issue of decidability.