sparsebit: Sparse bitmaps for pattern match coverage

[ bsd3, data-structures, development, library ] [ Propose Tags ]

Pattern matching coverage over Algebraic Data Types(ADTs) has most often been studied in the context of pattern compilation algorithms. However, it is worth considering the pattern matching coverage problem in isolation, since general solutions will be independent of the specifics of any implementation or language. We define an intuitive and mathematically well-established bit masking semantics for pattern match coverage. We design and implement a sparse bitmap data structure, which realizes this semantics in a compact and flexible manner. This bitmap data structure supports computing coverage solutions of large programs incrementally from coverage solutions of sub-programs. It can also be used as a common data representation for pattern coverage shared between different tools (e.g., compilers, linting tools, software analysis tools) that need pattern match coverage information.


[Skip to Readme]

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.2, 0.3, 0.5
Dependencies base, haskell98 [details]
License BSD-3-Clause
Author Ahn, Ki Yung
Maintainer Ahn, Ki Yung <kya@pdx.edu>
Category Development, Data Structures
Home page http://kyagrd.dyndns.org/wiki/SparseBitmapsForPatternMatchCoverage
Uploaded by KiYungAhn at 2009-03-10T09:53:49Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 3054 total (11 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for sparsebit-0.5

[back to package description]
Sparse Bitmaps for Pattern Match Coverage

Abstract:
  Pattern matching coverage over Algebraic Data Types(ADTs) has most often been studied in the context of pattern compilation algorithms. However, it is worth considering the pattern matching coverage problem in isolation, since general solutions will be independent of the specifics of any implementation or language.
  We define an intuitive and mathematically well-established bit masking semantics for pattern match coverage. We design and implement a sparse bitmap data structure, which realizes this semantics in a compact and flexible manner. This bitmap data structure supports computing coverage solutions of large programs incrementally from coverage solutions of sub-programs. It can also be used as a common data representation for pattern coverage shared between different tools (e.g., compilers, linting tools, software analysis tools) that need pattern match coverage information.


You can see further details in the paper and the talk slides on the this URL:
  http://kyagrd.dyndns.org/wiki/SparseBitmapsForPatternMatchCoverage


Additional source files Type.hs and TestType.hs packaged with this library
provides the examples and QuickCheck extracted from the paper to demonstrate
how to use this library.