Skip to content

Non redundant set#269

Merged
lucaneg merged 17 commits intolisa-analyzer:masterfrom
matteboro:nonRedundantSet
Jan 24, 2023
Merged

Non redundant set#269
lucaneg merged 17 commits intolisa-analyzer:masterfrom
matteboro:nonRedundantSet

Conversation

@matteboro
Copy link
Contributor

Description
This pull request adds three classes that can be used to create the lattice of the non redundant set of elements of another lattice's domain. These classes provides the methods necessary for the definition of the classical operations on elements of a lattice (such as lub, glb, widening, narrowing, less or equal). These methods includes a method that given a set create an equivalent set that is not redundant, an extrapolation heuristic that is used for the definiton of the widening operator, an Egli-Milner less or equal relation method and an Egli-Milner connector method that given two sets it yields a new set that is in the Egli-Milner less or equal relation with the two.
The pull request also adds the NonRedundantPowersetOfInterval which defines a non relational value abstract domain whose domain is all the sets of non redundant sets on intervals.

Implemented features
this pull request adds 4 classes:

  • NonRedundantPowerset: it generalizes the concept of non redundant powerset of the domain of a lattice (this lattice can be both relation or non-relational).
  • ValueNonRedundantPowerset: it is a NonRedundantPowerset, but only accepts ValueDomain an ValueExpressions.
  • NonRedundantPowersetOfBaseNonRelationalValueDomain: this class is specific for BaseNonRelationalValueDomain.
  • NonRedundantPowersetOfInterval

Further content
This pull request follows this paper: https://www.cs.unipr.it/Publications/PDF/Q349.pdf

@matteboro matteboro requested a review from lucaneg as a code owner January 19, 2023 15:15
@VincenzoArceri VincenzoArceri added 🎆 type:feature New feature or request 🔍 scope:analysis Work regarding abstract domains or fixpoint algorithms labels Jan 20, 2023
@VincenzoArceri VincenzoArceri added this to the 0.1b8 milestone Jan 20, 2023
@lucaneg lucaneg merged commit d357d11 into lisa-analyzer:master Jan 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

🔍 scope:analysis Work regarding abstract domains or fixpoint algorithms 🎆 type:feature New feature or request

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants