russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
88 lines
3.6 KiB
ReStructuredText
88 lines
3.6 KiB
ReStructuredText
Haskell — CWE-407 Language Analysis
|
||
=====================================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
Haskell's ``elem :: Eq a => a -> [a] -> Bool`` function (and its operator form `` x \`elem\` xs ``)
|
||
performs a linear scan of a list. This is O(n) by definition — Haskell lists are singly-linked,
|
||
so membership can only be determined by traversal. The function is universally available and
|
||
idiomatically natural; this makes it the canonical CWE-407 source in Haskell.
|
||
|
||
The fix is to use ``Data.Set.member :: Ord a => a -> Set a -> Bool`` (O(log n), balanced BST)
|
||
or ``Data.HashMap.Strict.member :: (Eq k, Hashable k) => k -> HashMap k v -> Bool`` (O(1)
|
||
amortized). For the specific use case of cycle detection and visited-node tracking, neither the
|
||
ordering constraint of ``Data.Set`` nor the ``Hashable`` constraint of ``Data.HashMap`` is
|
||
onerous — node identity (``Eq``, ``Ord``, or explicit node IDs) is always available.
|
||
|
||
GHC itself carries four instances of this defect: see :doc:`../compiler/ghc`.
|
||
|
||
Canonical Defect Pattern
|
||
------------------------
|
||
|
||
.. code-block:: haskell
|
||
|
||
-- Defective — O(V²)
|
||
import Data.List (elem)
|
||
|
||
dfs :: Graph -> [Vertex] -> Vertex -> [Vertex]
|
||
dfs graph visited v
|
||
| v `elem` visited = visited -- O(|visited|) per call
|
||
| otherwise = foldl (dfs graph) (v : visited) (neighbors graph v)
|
||
|
||
.. code-block:: haskell
|
||
|
||
-- Fixed — O(V log V) with Data.Set
|
||
import qualified Data.Set as Set
|
||
|
||
dfs :: Graph -> Set.Set Vertex -> Vertex -> Set.Set Vertex
|
||
dfs graph visited v
|
||
| Set.member v visited = visited -- O(log V) per call
|
||
| otherwise = foldl (dfs graph)
|
||
(Set.insert v visited)
|
||
(neighbors graph v)
|
||
|
||
.. code-block:: haskell
|
||
|
||
-- Fixed — O(V) with Data.HashMap (if Hashable instance available)
|
||
import qualified Data.HashMap.Strict as HashMap
|
||
|
||
dfs :: Graph -> HashMap.HashMap Vertex () -> Vertex -> HashMap.HashMap Vertex ()
|
||
dfs graph visited v
|
||
| HashMap.member v visited = visited -- O(1) amortized
|
||
| otherwise = foldl (dfs graph)
|
||
(HashMap.insert v () visited)
|
||
(neighbors graph v)
|
||
|
||
Confirmed Defects
|
||
-----------------
|
||
|
||
Four defects in GHC, covering SCC decode, edge-existence testing, register allocation, and
|
||
type-class constructor checking. All unpatched. See :doc:`../compiler/ghc` for full analysis.
|
||
|
||
| Defect | File | Complexity | Status |
|
||
|---------|-----------------------------------------|---------------------|-----------|
|
||
| ghc-0001| ``Directed/Internal.hs:78`` | O(V × degree) | Unpatched |
|
||
| ghc-0002| ``Inductive/Graph.hs:489-501`` | O(degree) per query | Unpatched |
|
||
| ghc-0003| ``Graph/Ops.hs:637`` | O(deg²) per func | Unpatched |
|
||
| ghc-0004| ``Tc/TyCl/Utils.hs:973`` | O(V²) | Unpatched |
|
||
|
||
Ecosystem Note
|
||
--------------
|
||
|
||
GHC's own internal use of ``elem`` for cycle detection is ironic: the compiler that compiles
|
||
Haskell programs carries the canonical Haskell O(n) membership defect. The ``Data.Graph`` module
|
||
in the Haskell ``containers`` library (which GHC bundles) is correctly implemented using arrays
|
||
and integer indices — GHC's defective sites are in the middle-end compiler passes, not in the
|
||
base library.
|
||
|
||
Note: Erlang OTP's ``beam_digraph.erl`` (internal VM module, OTP 22+) is correctly implemented
|
||
with maps/sets. The defective sites are in the ``digraph`` and ``digraph_utils`` stdlib modules
|
||
that predate OTP 22.
|
||
|
||
References
|
||
----------
|
||
|
||
* :doc:`../compiler/ghc`
|