package goblint

  1. Overview
  2. Docs
Static analysis framework for C

Install 

dune-project
 Dependency

goblint.in.tum.de Readme Changelog Edit opam file Versions (9)

Authors

  1. S
    Simmo Saan
  2. M
    Michael Schwarz
  3. J
    Julian Erhard
  4. S
    Sarah Tilscher
  5. K
    Karoliine Holter
  6. R
    Ralf Vogler
  7. K
    Kalmer Apinis
  8. V
    Vesal Vojdani

Maintainers

  1. S
    Simmo Saan <simmo.saan@gmail.com>
  2. M
    Michael Schwarz <michael.schwarz93@gmail.com>
  3. K
    Karoliine Holter <karoliine.holter@ut.ee>

Sources

goblint-2.6.0.tbz
sha256=20d5b7332a9f6072ab9ba86c4a53b898eaf681286c56a8805c41850bbf3ddf41
sha512=7c7685cfcd9aa866bc40e813df2bfcb3c79b3d40e615d8d6d0939c5798b9d70dd7f2ba87a741f5ba0ce891e9d254627207fb28057f1f2f6611e4e0d128fd6a71

doc/goblint.lib/Goblint_lib/CongruenceClosure/MRMap/index.html

Module CongruenceClosure.MRMap

Minimal representatives map. It maps each representative term of an equivalence class to the minimal term of this representative class. rep -> (t, z) means that t = rep + z

type t = (T.t * Z.t) TMap.t
val equal : t -> t -> Ppx_deriving_runtime.bool
val compare : t -> t -> Ppx_deriving_runtime.int
val hash : t -> int
val bindings : 'a TMap.t -> (TMap.key * 'a) list
val find : TMap.key -> 'a TMap.t -> 'a
val find_opt : TMap.key -> 'a TMap.t -> 'a option
val add : TMap.key -> 'a -> 'a TMap.t -> 'a TMap.t
val remove : TMap.key -> 'a TMap.t -> 'a TMap.t
val mem : TMap.key -> 'a TMap.t -> bool
val empty : 'a TMap.t
val show_min_rep : (T.t * Z.t) TMap.t -> string
val update_min_repr : (((Goblint_lib__UnionFind.term * Z.t) * 'a) TUF.ValMap.t * TSet.t * LMap.t) -> (term * Z.t) TMap.t -> TUF.ValMap.key list -> (term * Z.t) TMap.t

Uses dijkstra algorithm to update the minimal representatives of the successor nodes of all edges in the queue and if necessary it recursively updates the minimal representatives of the successor nodes. The states in the queue must already have an updated min_repr. This function visits only the successor nodes of the nodes in queue, not the nodes themselves. Before visiting the nodes, it sorts the queue by the size of the current mininmal representative.

parameters:

  • `(uf, set, map)` represent the union find data structure and the corresponding term set and lookup map.
  • `min_representatives` maps each representative of the union find data structure to the minimal representative of the equivalence class.
  • `queue` contains the states that need to be processed. The states of the automata are the equivalence classes and each state of the automata is represented by the representative term. Therefore the queue is a list of representative terms.

Returns:

  • The updated `min_representatives` map with the minimal representatives
val compute_minimal_representatives : (((Goblint_lib__UnionFind.term * Z.t) * 'a) TUF.ValMap.t * TSet.t * LMap.t) -> (term * Z.t) TMap.t
val initial_minimal_representatives : TSet.t -> (TMap.key * Z.t) TMap.t

Computes the initial map of minimal representatives. It maps each element `e` in the set to `(e, 0)`.