3 ms·

A coverage tool will not come remotely close to showing you untested paths. Array indexing, for example, is an implicit branch between every possible element i

A coverage tool will not come remotely close to showing you untested paths. Array indexing, for example, is an implicit branch between every possible element in the array, but most coverage tools I've seen count just evaluating the indexing expression as covering the line. On the other hand, judicious use of indexed data types can guarantee a data path for all indices into the array. Simple sum types like Maybe and Either guarantee a data path for the more simple use cases of null or errors. Uses of undefined functions and variables are not what people are talking about here (though those do happen in dynamic languages); we're talking about stuff that can't be checked locally (like "is a null allowed to come into the function at all, and if it does are you covering it") that are hard or impossible to catch with coverage tools.

kazinator 10y ago
If for some crazy reason we choose to regard an array access as if it were a big switch or case statement with a branch for each index, we are wrong in concluding that this creates a path coverage problem. These cases are machine-generated and do not require separate coverage treatment. An analogy might be found in, say, machine-unrolled loops. I don't care about coverage of multiple copies of a loop body caused by a compiler optimization.
- Jweb_Guru 10y ago
  How do you know that each array index will succeed, without a proof (or type) to that effect? You don't. You're arguing from the technical definition of path coverage (cases that are machine-generated "don't count"), but I'm arguing from "actually covering the behavior of your program," which means they absolutely do. You're also assuming that the behavior on failure will always be a crash, which isn't even close to being the worst kind of failure from an array index that returns something unexpected.
  - kazinator 10y ago
    I don't care about that within the scope of coverage testing. I am not laboring under any misconception that path coverage is correctness proof. Path coverage is not "coverage of the behavior of the program". My thesis is that path coverage will catch a type error, like a floating-point value being used as the array index, or a non-array being indexed. Programs have to be contrived to harbor a type error in spite of complete path coverage. Complete path coverage means this: every node of the program's graph has is visited at least once at run-time. At that visit, type is determined. This is similar to traversing the program graph statically and determining the type at each node. Regarding your last point, yes, I'm working under the assumption that we catch errors rather than behave unpredictably.
    - Jweb_Guru 10y ago
      You're assuming we are only talking about very simple types, and simple program semantics. In the vast majority of dynamic languages, variables are unityped with several tags (string, number, object, etc.) so they can trivially never experience a type error, with or without full path coverage (with the possible exception of attempting to access undefined variables, which is still not considered a type error in all languages). However, full path coverage does not guarantee that a value assigned a certain tag (which often drives which interfaces are provided) will have that same tag in all executions, and tags are often extremely imprecise descriptions of the value (often they are only precise enough to identify data layout), which means that many straightforward operations like property access and operator application have to be turned into potentially-throwing expressions or perform automatic casting to avoid causing a runtime error (both of which hinder many optimizations and making it hard to reason about your program's behavior). For instance, if you grab a value out of an array, assuming that the value you grab is an object with a certain property, and then access that property, requiring 100% path coverage still admits programs where the property will not be found (or where the property will be found, but have a different type than what is expected). Failing to account for the possibility that a tag is wrong is exactly what sum types rule out; failing to account for the existence of a property is what records (product types) rule out; the possibility of failing to grab an element from an array in the first place is what indexed data types (GADTs) rule out. None of these are type errors in most dynamic languages, and hence none can be replaced by 100% path coverage, except under very limited circumstances (which I can attest are not satisfied by real-world programs).

kazinator 10y ago

If for some crazy reason we choose to regard an array access as if it were a big switch or case statement with a branch for each index, we are wrong in concluding that this creates a path coverage problem. These cases are machine-generated and do not require separate coverage treatment. An analogy might be found in, say, machine-unrolled loops. I don't care about coverage of multiple copies of a loop body caused by a compiler optimization.

Jweb_Guru 10y ago
How do you know that each array index will succeed, without a proof (or type) to that effect? You don't. You're arguing from the technical definition of path coverage (cases that are machine-generated "don't count"), but I'm arguing from "actually covering the behavior of your program," which means they absolutely do. You're also assuming that the behavior on failure will always be a crash, which isn't even close to being the worst kind of failure from an array index that returns something unexpected.
- kazinator 10y ago
  I don't care about that within the scope of coverage testing. I am not laboring under any misconception that path coverage is correctness proof. Path coverage is not "coverage of the behavior of the program". My thesis is that path coverage will catch a type error, like a floating-point value being used as the array index, or a non-array being indexed. Programs have to be contrived to harbor a type error in spite of complete path coverage. Complete path coverage means this: every node of the program's graph has is visited at least once at run-time. At that visit, type is determined. This is similar to traversing the program graph statically and determining the type at each node. Regarding your last point, yes, I'm working under the assumption that we catch errors rather than behave unpredictably.
  - Jweb_Guru 10y ago
    You're assuming we are only talking about very simple types, and simple program semantics. In the vast majority of dynamic languages, variables are unityped with several tags (string, number, object, etc.) so they can trivially never experience a type error, with or without full path coverage (with the possible exception of attempting to access undefined variables, which is still not considered a type error in all languages). However, full path coverage does not guarantee that a value assigned a certain tag (which often drives which interfaces are provided) will have that same tag in all executions, and tags are often extremely imprecise descriptions of the value (often they are only precise enough to identify data layout), which means that many straightforward operations like property access and operator application have to be turned into potentially-throwing expressions or perform automatic casting to avoid causing a runtime error (both of which hinder many optimizations and making it hard to reason about your program's behavior). For instance, if you grab a value out of an array, assuming that the value you grab is an object with a certain property, and then access that property, requiring 100% path coverage still admits programs where the property will not be found (or where the property will be found, but have a different type than what is expected). Failing to account for the possibility that a tag is wrong is exactly what sum types rule out; failing to account for the existence of a property is what records (product types) rule out; the possibility of failing to grab an element from an array in the first place is what indexed data types (GADTs) rule out. None of these are type errors in most dynamic languages, and hence none can be replaced by 100% path coverage, except under very limited circumstances (which I can attest are not satisfied by real-world programs).