Yosys — CWE-407 Analysis
==========================

.. contents:: :local:

Overview
--------

Yosys is an open-source RTL synthesis framework used extensively in open-source FPGA
and ASIC flows. It performs logic optimization, technology mapping, and FSM extraction.
Its ``passes/cmds/scc`` pass implements Tarjan's SCC algorithm for combinational loop
detection. Its ``passes/opt/share`` pass performs cell-sharing optimization using DFS
traversal.

**Status: CLEAN — 0 confirmed defects**

Scanner returned 25 candidates; all are false positives on Yosys's ``pool<T>`` and
``dict<K,V>`` hash containers, which provide O(1) ``.count()``/``.insert()``.

Key Triage — SCC Pass
---------------------

The ``scc.cc`` Tarjan implementation is the highest-priority candidate. Full inspection
confirms it is **correct**::

   pool<RTLIL::Cell*>  workQueue;        // hash set — O(1) erase/count
   dict<RTLIL::Cell*, ...> cellLabels;   // hash map — O(1) count/insert
   pool<RTLIL::Cell*>  cellsOnStack;     // hash set — O(1) count/insert
   std::vector<RTLIL::Cell*> cellStack;  // ordered stack for pop — correct

   // Tarjan DFS:
   if (cellLabels.count(nextCell) == 0)     // O(1) — dict lookup
   if (cellsOnStack.count(nextCell) > 0)    // O(1) — pool lookup

``pool<T>`` is Yosys's hash-backed set (similar to ``std::unordered_set``). ``dict<K,V>``
is Yosys's hash map. Both provide O(1) amortized membership. This is a textbook-correct
Tarjan implementation.

Container Pattern Triage
------------------------

All 25 scanner candidates follow the same pattern — ``.count()`` on a ``pool<T>`` or
``dict<K,V>`` inside a graph traversal loop:

- ``fsm_opt.cc`` — ``std::set<int>`` for unreachable state IDs — O(log n) ✓
- ``share.cc`` — ``pool<RTLIL::Cell*> stop`` in DFS cone search — O(1) ✓
- ``opt_expr.cc``, ``ltp.cc``, ``recover_names.cc``, ``abc.cc``, ``abc9.cc``,
  ``abc9_ops.cc``, ``sat/`` — all ``dict``/``pool`` — O(1) ✓

One candidate uses ``std::find`` on a ``std::vector``:

- ``glift.cc:341`` — ``std::find(ports.begin(), ports.end(), name)`` — O(|ports|)
  **but** this is inside a ``log_assert()`` — assertion-only code that runs only in
  debug builds; port lists are single-digit in size; not a CWE-407 defect.

Design Assessment
-----------------

Yosys uses its own ``pool<T>`` / ``dict<K,V>`` / ``idict<T>`` container library
(``kernel/hashlib.h``) throughout all graph algorithms. These are open-addressed hash
containers with O(1) amortized operations. The design team intentionally chose these
over ``std::set``/``std::map`` for performance. The codebase is effectively immune to
the CWE-407 membership pattern.

References
----------

* Scanner: ``tools/scans/yosys.sh``
* Scan result: ``tools/scan-results/yosys.txt`` — 25 candidates, all false positives
* Container library: ``kernel/hashlib.h`` — ``pool<T>``, ``dict<K,V>``, ``idict<T>``
