Filters

Filters can be used to get a list of analyzed elements matching some constraints. Filters are useful to perform some checks on the analyzed code, for example to look for record fields never accessed (see examples).

The syntax of filters is described below. Applications using the Oug library can use the Oug_lang module to create and apply filters.

Syntax

Here is the syntax of filters, in BNF-like notation:

FILTER ::=
| FILTER '&' FILTER # intersection of elements matching each filter
| FILTER '|' FILTER # union of elements matching each filter
| '!' FILTER        # all elements except the ones matching the filter
| '(' FILTER ')'
| DEPEND FILTER     # all elements for which an edge (of the given dependency
                    # kind) points to at least one element matching the filter
                    # (let's call it the "ref" filter)
| FILTER DEPEND     # all elements for which an edge (of the given dependency
                    # kind) comes from at least one element matching the filter
                    # (let's call it the "from" filter)
| SELECTER
| "let" IDENTIFIER '=' FILTER "in" FILTER
| IDENTIFIER

DEPEND ::=
| '-'DEPKINDS'-''>'
| '-'DEPKINDS'{'DISTANCE'}''-''>'

DEPKINDS ::=
| DEPKIND
| DEPKIND '|' DEPKINDS # to indicate various possibility of dependency

DEPKIND ::= "Use" | "Contain" | "Include" | "Inherit" | "Alias" | "Export" | "Create"

DISTANCE ::=
| '+' # any number of edges >= 1
| INT # a specified number of edges

SELECTER ::= KINDS':'NAME | NAME
  # a selecter is used to retrieve a set of elements by name and/or kind

KINDS ::= ['v' 'M' 'C' 'm' 'i' 't' 'f' 'e' 'p']+':'
  # (v)alue, (M)odule, (C)lass, (m)ethod, (i)nstance variable,
  # (t)ype, type (f)ield, (e)xpression, (p)attern variable.

NAME ::= '<'['*' 'A'-'Z']['*' '\'' 'A'-'Z' 'a'-'z' '_' '.' '0'-'9']*'>'
  # the '*' can replace any element (use it like '.*' in a regexp)

INT ::= ['0'-'9']+

IDENTIFIER ::= ['a'-'z' 'A'-'Z']['A'-'Z' 'a'-'z' '_' '0'-'9']*
Examples

Here are some examples of filters. We suppose we have a dump of the analysis of our code in dump.oug, generated from this example with the command

# oug m6.ml --dump dump.oug

Let's print the list of modules:

#oug --load dump.oug --filter "M:<*>"
M:<*> (2 elements):
File "examples/m6.ml", line 1, char 0:
M6 [M]
File "examples/m6.ml", line 29, char 2:
M6.M [M]

We can provide various filters, for example to list the modules and the values:

#oug --load dump.oug --filter "M:<*>" --filter "v:<*>"
M:<*> (2 elements):
File "examples/m6.ml", line 1, char 0:
M6 [M]
File "examples/m6.ml", line 29, char 2:
M6.M [M]
v:<*> (10 elements):
File "examples/m6.ml", line 11, char 4:
M6.x [v]
File "examples/m6.ml", line 13, char 4:
M6.f [v]
File "examples/m6.ml", line 19, char 4:
M6.g [v]
File "examples/m6.ml", line 25, char 4:
M6.my_rec [v]
File "examples/m6.ml", line 26, char 18:
x [v]
File "examples/m6.ml", line 26, char 4:
M6.my_rec2 [v]
File "examples/m6.ml", line 33, char 4:
M6.f [v]
File "examples/m6.ml", line 41, char 4:
M6.x [v]
File "examples/m6.ml", line 45, char 4:
M6.x [v]
File "examples/m6.ml", line 48, char 4:
M6.f [v]

Let's ask something more precise, that is any element with a 'r' in its name, but which is not a type field. The "<*r*>" filter gets all elements with a 'r' in their name. The "f:<*>" filter returns all type fields. Then "! f:<*>" returns all elements except all type fields. We also compute "! e:<*>" to remove expression nodes from the result. Finally, '&' return the intersection of the three sets:

# oug --load dump.oug --filter  "<*r*> & (! f:<*>) & (! e:<*>)"
 (<*r*> & (!f:<*> & !e:<*>)) (4 elements):
File "_none_", line 1, char -1:
M6.trec [t]
File "examples/m6.ml", line 25, char 4:
M6.my_rec [v]
File "examples/m6.ml", line 26, char 4:
M6.my_rec2 [v]
File "_none_", line 1, char -1:
M6.M.tvar [t]

As you can see, some elements don't have location information. This is due to location information (by now) missing in the OCaml typedtree.

A useful filter is the one returning the type fields that no element creates. It allows to detect useless variant constructors. First, let's use the "<*> -Create->" filter to get all elements "created". This returns type fields, or expressions which are type field identifiers, in "creation" position. Creating a type field means setting a record field or building a value using a variant constructor:

#oug --load dump.oug --filter  "<*> -Create->"
(<*> -Create->) (17 elements):
File "_none_", line 1, char -1:
M6.trec.label1 [f]
File "_none_", line 1, char -1:
M6.trec.label2 [f]
File "_none_", line 1, char -1:
M6.trec.label3 [f]
File "examples/m6.ml", line 11, char 8:
label1 [e]
File "examples/m6.ml", line 11, char 8:
label2 [e]
File "examples/m6.ml", line 11, char 8:
label3 [e]
File "examples/m6.ml", line 25, char 15:
label1 [e]
File "examples/m6.ml", line 25, char 15:
label2 [e]
File "examples/m6.ml", line 25, char 15:
label3 [e]
File "examples/m6.ml", line 26, char 34:
label1 [e]
File "examples/m6.ml", line 26, char 34:
label2 [e]
File "_none_", line 1, char -1:
M6.M.tvar.Un [f]
File "_none_", line 1, char -1:
M6.M.tvar.Trois [f]
File "_none_", line 1, char -1:
M6.foo.Rec [f]
File "examples/m6.ml", line 45, char 12:
label1 [e]
File "examples/m6.ml", line 45, char 12:
label2 [e]
File "examples/m6.ml", line 45, char 12:
label3 [e]

But we want the type fields not created, so we will take the complementary of the filter above, which will return all elements but the elements above, and take the intersection with all type fields:

#oug --load dump.oug --filter  "f:<*> & ! <*> -Create->"
(f:<*> & !(<*> -Create->)) (5 elements):
File "_none_", line 1, char -1:
M6.M.tvar.Zero [f]
File "_none_", line 1, char -1:
M6.M.tvar.Deux [f]
File "_none_", line 1, char -1:
M6.foo.Var [f]
File "_none_", line 1, char -1:
M6.foo.String [f]
File "_none_", line 1, char -1:
M6.t.field [f]

A similar filter can be used to detect type fields never "used" (not read for record fields, not pattern-matched for variant constructors):

#oug --load dump.oug --filter  "f:<*> & ! <*> -Use->"
(f:<*> & !(<*> -Use->)) (4 elements):
File "_none_", line 1, char -1:
M6.trec.label3 [f]
File "_none_", line 1, char -1:
M6.foo.Var [f]
File "_none_", line 1, char -1:
M6.foo.Rec [f]
File "_none_", line 1, char -1:
M6.foo.String [f]

A simple filter to get the elements of module M6, except expressions and pattern variables:

#oug --load dump.oug --filter "<M6> -Contain-> & ! e:<*> & ! p:<*>"
((<M6> -Contain->) & (!e:<*> & !p:<*>)) (14 elements):
File "_none_", line 1, char -1:
M6.trec [t]
File "examples/m6.ml", line 11, char 4:
M6.x [v]
File "examples/m6.ml", line 13, char 4:
M6.f [v]
File "examples/m6.ml", line 19, char 4:
M6.g [v]
File "examples/m6.ml", line 25, char 4:
M6.my_rec [v]
File "examples/m6.ml", line 26, char 18:
x [v]
File "examples/m6.ml", line 26, char 4:
M6.my_rec2 [v]
File "examples/m6.ml", line 29, char 2:
M6.M [M]
File "examples/m6.ml", line 33, char 4:
M6.f [v]
File "examples/m6.ml", line 41, char 4:
M6.x [v]
File "_none_", line 1, char -1:
M6.foo [t]
File "examples/m6.ml", line 45, char 4:
M6.x [v]
File "_none_", line 1, char -1:
M6.t [t]
File "examples/m6.ml", line 48, char 4:
M6.f [v]

Getting the list of elements not "used" is as simple as:

# oug --load dump.oug --filter "! <*>-Use-> & ! e:<*>"
 (!(<*> -Use->) & !e:<*>) (17 elements):
File "examples/m6.ml", line 1, char 0:
M6 [M]
File "_none_", line 1, char -1:
M6.trec.label3 [f]
File "examples/m6.ml", line 11, char 4:
M6.x [v]
File "examples/m6.ml", line 15, char 13:
s [p]
File "examples/m6.ml", line 13, char 4:
M6.f [v]
File "examples/m6.ml", line 21, char 13:
s [p]
File "examples/m6.ml", line 19, char 4:
M6.g [v]
File "examples/m6.ml", line 26, char 4:
M6.my_rec2 [v]
File "examples/m6.ml", line 29, char 2:
M6.M [M]
File "examples/m6.ml", line 41, char 4:
M6.x [v]
File "_none_", line 1, char -1:
M6.foo [t]
File "_none_", line 1, char -1:
M6.foo.Var [f]
File "_none_", line 1, char -1:
M6.foo.Rec [f]
File "_none_", line 1, char -1:
M6.foo.String [f]
File "examples/m6.ml", line 45, char 4:
M6.x [v]
File "_none_", line 1, char -1:
M6.t [t]
File "examples/m6.ml", line 48, char 4:
M6.f [v]

Note the difference between "<*> -Use->" and "-Use-> <*>". The first filter selects the elements "being used" (or being contained when "Contain" is used instead of "Use") by any element while the second filter selects the elements "using" any element.

The following filter gets the elements which use some type fields not created in the module (we get the expressions referring to such type fields):

#oug --load dump.oug --filter "-Use-> ((! <*> -Create->) & f:<*>)"
 (-Use-> (!(<*> -Create->) & f:<*>)) (3 elements):
File "examples/m6.ml", line 35, char 2:
Zero [e]
File "examples/m6.ml", line 37, char 2:
Deux [e]
File "examples/m6.ml", line 48, char 15:
field [e]

Some "distance" constraints can be specified on "ref" and "from" filters; the following command prints the list of elements using fields of M6.M.tvar or, recursively, elements using such elements:

#oug --load dump.oug --filter "-Use{+}-> <M6.M.tvar.*>"
(-Use{+}-> <M6.M.tvar.*>) (18 elements):
File "examples/m6.ml", line 1, char 0:
M6 [M]
File "examples/m6.ml", line 34, char 5:
n [p]
File "examples/m6.ml", line 34, char 2:
Un [e]
File "examples/m6.ml", line 34, char 12:
n [e]
File "examples/m6.ml", line 34, char 21:
n [e]
File "examples/m6.ml", line 35, char 2:
Zero [e]
File "examples/m6.ml", line 36, char 5:
n [p]
File "examples/m6.ml", line 36, char 2:
Un [e]
File "examples/m6.ml", line 36, char 10:
n [e]
File "examples/m6.ml", line 37, char 7:
n [p]
File "examples/m6.ml", line 37, char 2:
Deux [e]
File "examples/m6.ml", line 37, char 12:
n [e]
File "examples/m6.ml", line 38, char 8:
f [p]
File "examples/m6.ml", line 38, char 2:
Trois [e]
File "examples/m6.ml", line 38, char 26:
f [e]
File "examples/m6.ml", line 33, char 4:
M6.f [v]
File "examples/m6.ml", line 41, char 12:
f [e]
File "examples/m6.ml", line 41, char 4:
M6.x [v]

Various dependency kinds can be given on each "ref" and "from" filter; here we get the list of elements using or creating fields of the type M6.trec:

#oug --load dump.oug --filter "-Use|Create-> <M6.trec.*>"
(-Use|Create-> <M6.trec.*>) (20 elements):
File "examples/m6.ml", line 11, char 8:
label1 [e]
File "examples/m6.ml", line 11, char 8:
label2 [e]
File "examples/m6.ml", line 11, char 8:
label3 [e]
File "examples/m6.ml", line 14, char 2:
label1 [e]
File "examples/m6.ml", line 15, char 2:
label1 [e]
File "examples/m6.ml", line 15, char 2:
label2 [e]
File "examples/m6.ml", line 16, char 2:
label1 [e]
File "examples/m6.ml", line 20, char 2:
label1 [e]
File "examples/m6.ml", line 21, char 2:
label1 [e]
File "examples/m6.ml", line 21, char 2:
label2 [e]
File "examples/m6.ml", line 22, char 2:
label1 [e]
File "examples/m6.ml", line 25, char 15:
label1 [e]
File "examples/m6.ml", line 25, char 15:
label2 [e]
File "examples/m6.ml", line 25, char 15:
label3 [e]
File "examples/m6.ml", line 26, char 71:
label2 [e]
File "examples/m6.ml", line 26, char 34:
label1 [e]
File "examples/m6.ml", line 26, char 34:
label2 [e]
File "examples/m6.ml", line 45, char 12:
label1 [e]
File "examples/m6.ml", line 45, char 12:
label2 [e]
File "examples/m6.ml", line 45, char 12:
label3 [e]