package goblint

  1. Overview
  2. Docs
Static analysis framework for C

Install 

dune-project
 Dependency

goblint.in.tum.de Edit opam file Versions (11)

Authors

  1. S
    Simmo Saan
  2. M
    Michael Schwarz
  3. J
    Julian Erhard
  4. S
    Sarah Tilscher
  5. K
    Karoliine Holter
  6. M
    Michael Petter
  7. A
    Ali Rasim Kocal
  8. R
    Ralf Vogler
  9. K
    Kalmer Apinis
  10. 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.8.0.tbz
sha256=9175eec0143102243964e34a0786584fd590c60422009259c705a89a27f88de4
sha512=9d760007dd8d003cf596516444ed7acc7370fc3d446e75ac71b0176522c3baae090410762f9035e7aae4f6b0e394bf28bb5b1c08ca0476920b94aa919ef04f42

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)`.