Dynamic Dependency-Based Purity Checking

Abstract

Many software language tools use declarative domain-specific languages (DDSLs) to implement parts of their functionality, such as context-free grammars for parsing or inference rules for type analysis. For interoperability and ease of use, DDSLs often rely on embedded general-purpose language (GPL) code fragments, as in the semantic actions of parser specifications, but require that these GPL fragments fulfill certain semantic properties, such as the absence of observable side effects. Fulfilling these properties is usually up to the developer, and accidental violations can lead to subtle and hard-to-trace bugs.

We present Tragdor, a tool that dynamically checks for property violations in Reference Attribute Grammars (RAGs) written for the JastAdd metacompiler, and report on the efficacy of four property testing strategies that Tragdor employs. Even in a mature RAG like the Java 11 compiler ExtendJ, Tragdor was able to find 13 implementation issues, 2 of which we consider to be of high severity. Our manual inspection of Tragdor's reports identifies a number of potential RAG anti-patterns and finds evidence that the inherent dependency structure of RAGs often encodes fine-grained implicit contracts.