-
Notifications
You must be signed in to change notification settings - Fork 2k
Expand file tree
/
Copy pathDenseRank.qll
More file actions
129 lines (111 loc) · 3.13 KB
/
DenseRank.qll
File metadata and controls
129 lines (111 loc) · 3.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
* Provides modules for computing dense `rank`s. See the `DenseRank` module
* below for a more detailed explanation.
*/
/** Provides the input to `DenseRank`. */
signature module DenseRankInputSig {
/** An element that is ranked. */
bindingset[this]
class Ranked;
/** Gets the rank of `r`. */
int getRank(Ranked r);
}
/**
* Provides the `denseRank` predicate for computing dense `rank`s. For example,
* if we have
*
* ```ql
* query predicate names(string name) {
* name = ["Alice", "Bob", "Charles", "Charlie", "David"]
* }
*
* int rankByFirstLetter(string name) {
* name = rank[result](string n | names(n) | n order by n.charAt(0))
* }
* ```
*
* then `rankByFirstLetter` computes the following relation
*
* ```
* Alice 1
* Bob 2
* Charles 3
* Charlie 3
* David 5
* ```
*
* Note that `"David"` has rank 5 instead of 4. If we want a dense ranking instead,
* we can do
*
* ```ql
* module M implements DenseRankInputSig {
* class Ranked = string;
*
* predicate getRank = rankByFirstLetter/1;
* }
*
* predicate denseRank = DenseRank<M>::denseRank/1;
* ```
*/
module DenseRank<DenseRankInputSig Input> {
private import Input
private int rankRank(Ranked r, int rnk) {
rnk = getRank(r) and
rnk = rank[result](int rnk0 | rnk0 = getRank(_) | rnk0)
}
/** Gets the `Ranked` value for which the dense rank is `rnk`. */
Ranked denseRank(int rnk) { rnk = rankRank(result, getRank(result)) }
}
/** Provides the input to `DenseRank1`. */
signature module DenseRankInputSig1 {
/** A ranking context. */
bindingset[this]
class C;
/** An element that is ranked. */
bindingset[this]
class Ranked;
/** Gets the rank of `r` in the context provided by `c`. */
int getRank(C c, Ranked r);
}
/** Same as `DenseRank`, but allows for a context consisting of one element. */
module DenseRank1<DenseRankInputSig1 Input> {
private import Input
private int rankRank(C c, Ranked r, int rnk) {
rnk = getRank(c, r) and
rnk = rank[result](int rnk0 | rnk0 = getRank(c, _) | rnk0)
}
/**
* Gets the `Ranked` value for which the dense rank in the context provided by
* `c` is `rnk`.
*/
Ranked denseRank(C c, int rnk) { rnk = rankRank(c, result, getRank(c, result)) }
}
/** Provides the input to `DenseRank2`. */
signature module DenseRankInputSig2 {
/** A ranking context. */
bindingset[this]
class C1;
/** A ranking context. */
bindingset[this]
class C2;
/** An element that is ranked. */
bindingset[this]
class Ranked;
/** Gets the rank of `r` in the context provided by `c1` and `c2`. */
int getRank(C1 c1, C2 c2, Ranked r);
}
/** Same as `DenseRank`, but allows for a context consisting of two elements. */
module DenseRank2<DenseRankInputSig2 Input> {
private import Input
private int rankRank(C1 c1, C2 c2, Ranked r, int rnk) {
rnk = getRank(c1, c2, r) and
rnk = rank[result](int rnk0 | rnk0 = getRank(c1, c2, _) | rnk0)
}
/**
* Gets the `Ranked` value for which the dense rank in the context provided by
* `c1` and `c2` is `rnk`.
*/
Ranked denseRank(C1 c1, C2 c2, int rnk) {
rnk = rankRank(c1, c2, result, getRank(c1, c2, result))
}
}