| 1 |
|
| /* pmcp_uri.h - RFC 6570 level 1 URI templates, and base64 for blobs. |
| 2 |
|
| * |
| 3 |
|
| * Needs: pmcp_reg.h. |
| 4 |
|
| * Gives: pmcp_tpl (a parsed template), pmcp_tpl_parse, pmcp_tpl_match, |
| 5 |
|
| * pmcp_tpl_overlap, pmcp_tpl_free, pmcp_b64. |
| 6 |
|
| * |
| 7 |
|
| * Level 1 only: {var}, no operators and no modifiers (16). A variable's value |
| 8 |
|
| * is what simple expansion produces, so it never holds a raw '/', '?' or '#' |
| 9 |
|
| * (expansion percent-encodes them), and a match captures a run without them. |
| 10 |
|
| * Two variables must be separated by text, or the split between them would be |
| 11 |
|
| * a guess. |
| 12 |
|
| */ |
| 13 |
|
| |
| 14 |
|
| #ifndef PMCP_URI_H |
| 15 |
|
| #define PMCP_URI_H |
| 16 |
|
| |
| 17 |
|
| typedef struct { |
| 18 |
|
| int is_var; |
| 19 |
|
| char *text; /* the literal, or the variable's name */ |
| 20 |
|
| STRLEN len; |
| 21 |
|
| } pmcp_tok; |
| 22 |
|
| |
| 23 |
|
| typedef struct { |
| 24 |
|
| pmcp_tok *tok; |
| 25 |
|
| int n; |
| 26 |
|
| } pmcp_tpl; |
| 27 |
|
| |
| 28 |
49 |
| static void pmcp_tpl_free(pmcp_tpl *t) |
| 29 |
|
| { |
| 30 |
|
| int i; |
| 31 |
49 |
▶ | if (!t) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!t) return; |
0 |
49 |
49 |
|
| 32 |
147 |
▶ | for (i = 0; i < t->n; i++) Safefree(t->tok[i].text); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < t->n; i++) Safefree(t->tok[i].text); |
98 |
49 |
147 |
|
| 33 |
49 |
| Safefree(t->tok); |
| 34 |
49 |
| Safefree(t); |
| 35 |
|
| } |
| 36 |
|
| |
| 37 |
|
| /* Does the URI hold a template at all? */ |
| 38 |
110 |
| static int pmcp_is_template(const char *p, STRLEN l) |
| 39 |
|
| { |
| 40 |
110 |
▶ | return memchr(p, '{', l) != NULL || memchr(p, '}', l) != NULL; |
Branch: 2 branches
| Branch | True | False | Total |
| return memchr(p, '{', l) != NULL || memchr(p, '}', l) != NULL; |
53 |
57 |
110 |
| return memchr(p, '{', l) != NULL || memchr(p, '}', l) != NULL; |
1 |
52 |
53 |
|
| 41 |
|
| } |
| 42 |
|
| |
| 43 |
119 |
| static void pmcp_tpl_push(pmcp_tpl *t, int is_var, const char *p, STRLEN l) |
| 44 |
|
| { |
| 45 |
|
| pmcp_tok *k; |
| 46 |
119 |
| Renew(t->tok, t->n + 1, pmcp_tok); |
| 47 |
119 |
| k = &t->tok[t->n++]; |
| 48 |
119 |
| k->is_var = is_var; |
| 49 |
119 |
| k->len = l; |
| 50 |
119 |
| Newx(k->text, l + 1, char); |
| 51 |
119 |
| Copy(p, k->text, l, char); |
| 52 |
119 |
| k->text[l] = '\0'; |
| 53 |
119 |
| } |
| 54 |
|
| |
| 55 |
|
| /* Parse a template, or croak naming it and what is wrong. */ |
| 56 |
58 |
| static pmcp_tpl *pmcp_tpl_parse(pTHX_ SV *uri) |
| 57 |
|
| { |
| 58 |
58 |
| STRLEN l, i = 0, start = 0; |
| 59 |
58 |
| const char *p = SvPV_const(uri, l); |
| 60 |
|
| pmcp_tpl *t; |
| 61 |
58 |
| const char *why = NULL; |
| 62 |
|
| |
| 63 |
58 |
| Newxz(t, 1, pmcp_tpl); |
| 64 |
517 |
▶ | while (i < l && !why) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (i < l && !why) { |
469 |
48 |
517 |
| while (i < l && !why) { |
469 |
0 |
469 |
|
| 65 |
469 |
▶ | if (p[i] == '}') { why = "has a '}' with no '{'"; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (p[i] == '}') { why = "has a '}' with no '{'"; break; } |
1 |
468 |
469 |
|
| 66 |
468 |
▶ | if (p[i] != '{') { i++; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (p[i] != '{') { i++; continue; } |
407 |
61 |
468 |
|
| 67 |
61 |
▶ | if (i > start) pmcp_tpl_push(t, 0, p + start, i - start); |
Branch: 1 branch
| Branch | True | False | Total |
| if (i > start) pmcp_tpl_push(t, 0, p + start, i - start); |
60 |
1 |
61 |
|
| 68 |
1 |
▶ | else if (t->n && t->tok[t->n - 1].is_var) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if (t->n && t->tok[t->n - 1].is_var) { |
1 |
0 |
1 |
| else if (t->n && t->tok[t->n - 1].is_var) { |
1 |
0 |
1 |
|
| 69 |
1 |
| why = "has two variables with no text between them"; |
| 70 |
1 |
| break; |
| 71 |
|
| } |
| 72 |
|
| { |
| 73 |
60 |
| STRLEN j = i + 1; |
| 74 |
60 |
▶ | if (j < l && strchr("+#./;?&=,!@|", p[j])) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (j < l && strchr("+#./;?&=,!@|", p[j])) { |
60 |
0 |
60 |
| if (j < l && strchr("+#./;?&=,!@|", p[j])) { |
2 |
58 |
60 |
|
| 75 |
2 |
| why = "uses an operator, and only level 1 {var} is supported"; |
| 76 |
2 |
| break; |
| 77 |
|
| } |
| 78 |
156 |
▶ | while (j < l && p[j] != '}') { |
Branch: 2 branches
| Branch | True | False | Total |
| while (j < l && p[j] != '}') { |
155 |
1 |
156 |
| while (j < l && p[j] != '}') { |
101 |
54 |
155 |
|
| 79 |
101 |
| char c = p[j]; |
| 80 |
101 |
▶ | if (c == ':' || c == '*') { |
Branch: 2 branches
| Branch | True | False | Total |
| if (c == ':' || c == '*') { |
100 |
1 |
101 |
| if (c == ':' || c == '*') { |
1 |
99 |
100 |
|
| 81 |
2 |
| why = "uses a modifier, and only level 1 {var} is supported"; |
| 82 |
2 |
| break; |
| 83 |
|
| } |
| 84 |
100 |
▶ | if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
Branch: 5 branches
| Branch | True | False | Total |
| if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
98 |
1 |
99 |
| if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
98 |
0 |
98 |
| if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
98 |
1 |
99 |
| if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
0 |
98 |
98 |
| if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') |
1 |
0 |
1 |
|
| 85 |
1 |
▶ | || (c >= '0' && c <= '9') || c == '_')) { |
Branch: 2 branches
| Branch | True | False | Total |
| || (c >= '0' && c <= '9') || c == '_')) { |
0 |
1 |
1 |
| || (c >= '0' && c <= '9') || c == '_')) { |
0 |
0 |
0 |
|
| 86 |
1 |
| why = "has a variable name that is not letters, digits and _"; |
| 87 |
1 |
| break; |
| 88 |
|
| } |
| 89 |
98 |
| j++; |
| 90 |
|
| } |
| 91 |
58 |
▶ | if (why) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (why) break; |
3 |
55 |
58 |
|
| 92 |
55 |
▶ | if (j >= l) { why = "has a '{' with no '}'"; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (j >= l) { why = "has a '{' with no '}'"; break; } |
1 |
54 |
55 |
|
| 93 |
54 |
▶ | if (j == i + 1) { why = "has an empty {}"; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (j == i + 1) { why = "has an empty {}"; break; } |
1 |
53 |
54 |
|
| 94 |
|
| { |
| 95 |
|
| int k; |
| 96 |
110 |
▶ | for (k = 0; k < t->n; k++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < t->n; k++) |
58 |
52 |
110 |
|
| 97 |
58 |
▶ | if (t->tok[k].is_var && t->tok[k].len == j - i - 1 |
Branch: 2 branches
| Branch | True | False | Total |
| if (t->tok[k].is_var && t->tok[k].len == j - i - 1 |
3 |
55 |
58 |
| if (t->tok[k].is_var && t->tok[k].len == j - i - 1 |
3 |
0 |
3 |
|
| 98 |
3 |
▶ | && memEQ(t->tok[k].text, p + i + 1, j - i - 1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| && memEQ(t->tok[k].text, p + i + 1, j - i - 1)) { |
1 |
2 |
3 |
|
| 99 |
1 |
| why = "uses one variable name twice"; |
| 100 |
1 |
| break; |
| 101 |
|
| } |
| 102 |
53 |
▶ | if (why) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (why) break; |
1 |
52 |
53 |
|
| 103 |
|
| } |
| 104 |
52 |
| pmcp_tpl_push(t, 1, p + i + 1, j - i - 1); |
| 105 |
52 |
| i = start = j + 1; |
| 106 |
|
| } |
| 107 |
|
| } |
| 108 |
58 |
▶ | if (!why && start < l) pmcp_tpl_push(t, 0, p + start, l - start); |
Branch: 2 branches
| Branch | True | False | Total |
| if (!why && start < l) pmcp_tpl_push(t, 0, p + start, l - start); |
48 |
10 |
58 |
| if (!why && start < l) pmcp_tpl_push(t, 0, p + start, l - start); |
7 |
41 |
48 |
|
| 109 |
58 |
▶ | if (why) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (why) { |
10 |
48 |
58 |
|
| 110 |
10 |
| pmcp_tpl_free(t); |
| 111 |
10 |
| croak("%s: mcp resource '%" SVf "' %s", PMCP_WHO, SVfARG(uri), why); |
| 112 |
|
| } |
| 113 |
48 |
| return t; |
| 114 |
|
| } |
| 115 |
|
| |
| 116 |
|
| /* ---- matching -------------------------------------------------------------- */ |
| 117 |
|
| |
| 118 |
2539 |
| static int pmcp_var_char_ok(char c) |
| 119 |
|
| { |
| 120 |
2539 |
▶ | return c != '/' && c != '?' && c != '#'; |
Branch: 3 branches
| Branch | True | False | Total |
| return c != '/' && c != '?' && c != '#'; |
2506 |
33 |
2539 |
| return c != '/' && c != '?' && c != '#'; |
2505 |
1 |
2506 |
| return c != '/' && c != '?' && c != '#'; |
2505 |
0 |
2505 |
|
| 121 |
|
| } |
| 122 |
|
| |
| 123 |
16 |
| static int pmcp_hexval(char c) |
| 124 |
|
| { |
| 125 |
16 |
▶ | if (c >= '0' && c <= '9') return c - '0'; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c >= '0' && c <= '9') return c - '0'; |
16 |
0 |
16 |
| if (c >= '0' && c <= '9') return c - '0'; |
8 |
8 |
16 |
|
| 126 |
8 |
▶ | if (c >= 'a' && c <= 'f') return c - 'a' + 10; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c >= 'a' && c <= 'f') return c - 'a' + 10; |
2 |
6 |
8 |
| if (c >= 'a' && c <= 'f') return c - 'a' + 10; |
0 |
2 |
2 |
|
| 127 |
8 |
▶ | if (c >= 'A' && c <= 'F') return c - 'A' + 10; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c >= 'A' && c <= 'F') return c - 'A' + 10; |
8 |
0 |
8 |
| if (c >= 'A' && c <= 'F') return c - 'A' + 10; |
6 |
2 |
8 |
|
| 128 |
2 |
| return -1; |
| 129 |
|
| } |
| 130 |
|
| |
| 131 |
|
| /* Percent-decode p[0..l) into a new SV, or NULL for a malformed escape. */ |
| 132 |
18 |
| static SV *pmcp_pct_decode(pTHX_ const char *p, STRLEN l) |
| 133 |
|
| { |
| 134 |
18 |
| SV *out = newSV(l + 1); |
| 135 |
18 |
| char *d = SvPVX(out); |
| 136 |
18 |
| STRLEN i, o = 0; |
| 137 |
2166 |
▶ | for (i = 0; i < l; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < l; i++) { |
2150 |
16 |
2166 |
|
| 138 |
2150 |
▶ | if (p[i] == '%') { |
Branch: 1 branch
| Branch | True | False | Total |
| if (p[i] == '%') { |
9 |
2141 |
2150 |
|
| 139 |
|
| int hi, lo; |
| 140 |
9 |
▶ | if (i + 2 >= l) { SvREFCNT_dec(out); return NULL; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (i + 2 >= l) { SvREFCNT_dec(out); return NULL; } |
1 |
8 |
9 |
|
| 141 |
8 |
| hi = pmcp_hexval(p[i + 1]); |
| 142 |
8 |
| lo = pmcp_hexval(p[i + 2]); |
| 143 |
8 |
▶ | if (hi < 0 || lo < 0) { SvREFCNT_dec(out); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (hi < 0 || lo < 0) { SvREFCNT_dec(out); return NULL; } |
7 |
1 |
8 |
| if (hi < 0 || lo < 0) { SvREFCNT_dec(out); return NULL; } |
0 |
7 |
7 |
|
| 144 |
7 |
| d[o++] = (char)(hi * 16 + lo); |
| 145 |
7 |
| i += 2; |
| 146 |
|
| } |
| 147 |
2141 |
| else d[o++] = p[i]; |
| 148 |
|
| } |
| 149 |
16 |
| d[o] = '\0'; |
| 150 |
16 |
| SvPOK_on(out); |
| 151 |
16 |
| SvCUR_set(out, o); |
| 152 |
|
| /* a decoded value that is UTF-8 is characters, as a route capture is */ |
| 153 |
16 |
▶ | if (is_utf8_string((U8 *)d, o)) SvUTF8_on(out); |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_utf8_string((U8 *)d, o)) SvUTF8_on(out); |
16 |
0 |
16 |
|
| 154 |
16 |
| return out; |
| 155 |
|
| } |
| 156 |
|
| |
| 157 |
94 |
| static int pmcp_tpl_match_at(pTHX_ const pmcp_tpl *t, int k, const char *s, |
| 158 |
|
| STRLEN l, STRLEN pos, HV *caps) |
| 159 |
|
| { |
| 160 |
|
| const pmcp_tok *tk; |
| 161 |
94 |
▶ | if (k == t->n) return pos == l; |
Branch: 1 branch
| Branch | True | False | Total |
| if (k == t->n) return pos == l; |
17 |
77 |
94 |
|
| 162 |
77 |
| tk = &t->tok[k]; |
| 163 |
77 |
▶ | if (!tk->is_var) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tk->is_var) { |
53 |
24 |
77 |
|
| 164 |
53 |
▶ | if (l - pos < tk->len || memNE(s + pos, tk->text, tk->len)) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (l - pos < tk->len || memNE(s + pos, tk->text, tk->len)) return 0; |
49 |
4 |
53 |
| if (l - pos < tk->len || memNE(s + pos, tk->text, tk->len)) return 0; |
25 |
24 |
49 |
|
| 165 |
24 |
| return pmcp_tpl_match_at(aTHX_ t, k + 1, s, l, pos + tk->len, caps); |
| 166 |
|
| } |
| 167 |
|
| { |
| 168 |
|
| /* a variable runs to the next literal (the parser guarantees one |
| 169 |
|
| * follows, or this is the last token), trying each place it occurs */ |
| 170 |
|
| STRLEN e; |
| 171 |
2183 |
▶ | for (e = pos + 1; e <= l; e++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (e = pos + 1; e <= l; e++) { |
2181 |
2 |
2183 |
|
| 172 |
2181 |
▶ | if (!pmcp_var_char_ok(s[e - 1])) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!pmcp_var_char_ok(s[e - 1])) return 0; |
4 |
2177 |
2181 |
|
| 173 |
2180 |
▶ | if (k + 1 == t->n ? e == l |
Branch: 2 branches
| Branch | True | False | Total |
| if (k + 1 == t->n ? e == l |
2174 |
3 |
2177 |
| if (k + 1 == t->n ? e == l |
19 |
2158 |
2177 |
|
| 174 |
3 |
| : (l - e >= t->tok[k + 1].len |
| 175 |
3 |
▶ | && memEQ(s + e, t->tok[k + 1].text, t->tok[k + 1].len))) { |
Branch: 2 branches
| Branch | True | False | Total |
| && memEQ(s + e, t->tok[k + 1].text, t->tok[k + 1].len))) { |
3 |
0 |
3 |
| && memEQ(s + e, t->tok[k + 1].text, t->tok[k + 1].len))) { |
2 |
1 |
3 |
|
| 176 |
19 |
▶ | if (pmcp_tpl_match_at(aTHX_ t, k + 1, s, l, e, caps)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (pmcp_tpl_match_at(aTHX_ t, k + 1, s, l, e, caps)) { |
18 |
1 |
19 |
|
| 177 |
18 |
| SV *v = pmcp_pct_decode(aTHX_ s + pos, e - pos); |
| 178 |
18 |
▶ | if (!v) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!v) return 0; |
2 |
16 |
18 |
|
| 179 |
16 |
| (void)hv_store(caps, tk->text, (I32)tk->len, v, 0); |
| 180 |
16 |
| return 1; |
| 181 |
|
| } |
| 182 |
|
| } |
| 183 |
|
| } |
| 184 |
2 |
| return 0; |
| 185 |
|
| } |
| 186 |
|
| } |
| 187 |
|
| |
| 188 |
|
| /* Match `uri` against `t`. Returns a new HV of decoded variables (+1), or |
| 189 |
|
| * NULL when it does not match. */ |
| 190 |
51 |
| static HV *pmcp_tpl_match(pTHX_ const pmcp_tpl *t, SV *uri) |
| 191 |
|
| { |
| 192 |
|
| STRLEN l; |
| 193 |
51 |
| const char *s = SvPV_const(uri, l); |
| 194 |
51 |
| HV *caps = newHV(); |
| 195 |
51 |
▶ | if (pmcp_tpl_match_at(aTHX_ t, 0, s, l, 0, caps)) return caps; |
Branch: 1 branch
| Branch | True | False | Total |
| if (pmcp_tpl_match_at(aTHX_ t, 0, s, l, 0, caps)) return caps; |
15 |
36 |
51 |
|
| 196 |
36 |
| SvREFCNT_dec((SV *)caps); |
| 197 |
36 |
| return NULL; |
| 198 |
|
| } |
| 199 |
|
| |
| 200 |
|
| /* ---- overlap --------------------------------------------------------------- */ |
| 201 |
|
| |
| 202 |
|
| /* Could one URI match both templates? A walk over pairs of positions, one per |
| 203 |
|
| * template, reading the same character at each step. A position is a token |
| 204 |
|
| * and, inside a variable, whether it has taken a character yet. The |
| 205 |
|
| * characters tried are those of both templates' literals plus one that is in |
| 206 |
|
| * neither, which stands for every other character a variable can take. */ |
| 207 |
|
| typedef struct { int k; int in; } pmcp_pos; |
| 208 |
|
| |
| 209 |
1278 |
| static int pmcp_step(const pmcp_tpl *t, pmcp_pos at, char c, pmcp_pos *out) |
| 210 |
|
| { |
| 211 |
1278 |
| int n = 0; |
| 212 |
1278 |
▶ | if (at.k >= t->n) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (at.k >= t->n) return 0; |
135 |
1143 |
1278 |
|
| 213 |
1143 |
▶ | if (t->tok[at.k].is_var) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t->tok[at.k].is_var) { |
344 |
799 |
1143 |
|
| 214 |
344 |
▶ | if (pmcp_var_char_ok(c)) { out[n].k = at.k; out[n].in = 1; n++; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (pmcp_var_char_ok(c)) { out[n].k = at.k; out[n].in = 1; n++; } |
314 |
30 |
344 |
|
| 215 |
|
| } |
| 216 |
799 |
▶ | else if ((STRLEN)at.in < t->tok[at.k].len && t->tok[at.k].text[at.in] == c) { |
Branch: 2 branches
| Branch | True | False | Total |
| else if ((STRLEN)at.in < t->tok[at.k].len && t->tok[at.k].text[at.in] == c) { |
799 |
0 |
799 |
| else if ((STRLEN)at.in < t->tok[at.k].len && t->tok[at.k].text[at.in] == c) { |
111 |
688 |
799 |
|
| 217 |
|
| /* inside a literal, `in` is the offset reached */ |
| 218 |
111 |
▶ | if ((STRLEN)at.in + 1 == t->tok[at.k].len) { out[n].k = at.k + 1; out[n].in = 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if ((STRLEN)at.in + 1 == t->tok[at.k].len) { out[n].k = at.k + 1; out[n].in = 0; } |
22 |
89 |
111 |
|
| 219 |
89 |
| else { out[n].k = at.k; out[n].in = at.in + 1; } |
| 220 |
111 |
| n++; |
| 221 |
|
| } |
| 222 |
1143 |
| return n; |
| 223 |
|
| } |
| 224 |
|
| |
| 225 |
|
| /* A variable that has taken a character may end there. */ |
| 226 |
302 |
| static int pmcp_close(const pmcp_tpl *t, pmcp_pos at, pmcp_pos *out) |
| 227 |
|
| { |
| 228 |
302 |
| int n = 0; |
| 229 |
302 |
| out[n++] = at; |
| 230 |
302 |
▶ | if (at.k < t->n && t->tok[at.k].is_var && at.in) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (at.k < t->n && t->tok[at.k].is_var && at.in) { |
297 |
5 |
302 |
| if (at.k < t->n && t->tok[at.k].is_var && at.in) { |
202 |
95 |
297 |
| if (at.k < t->n && t->tok[at.k].is_var && at.in) { |
188 |
14 |
202 |
|
| 231 |
188 |
| out[n].k = at.k + 1; |
| 232 |
188 |
| out[n].in = 0; |
| 233 |
188 |
| n++; |
| 234 |
|
| } |
| 235 |
302 |
| return n; |
| 236 |
|
| } |
| 237 |
|
| |
| 238 |
14 |
| static int pmcp_tpl_overlap(const pmcp_tpl *a, const pmcp_tpl *b) |
| 239 |
|
| { |
| 240 |
|
| char alpha[256]; |
| 241 |
14 |
| int na = 0, i, c; |
| 242 |
14 |
| int wa = a->n + 1, wb = b->n + 1; |
| 243 |
14 |
| STRLEN maxa = 1, maxb = 1; |
| 244 |
|
| char *seen; |
| 245 |
14 |
| int *queue, qh = 0, qt = 0, found = 0; |
| 246 |
|
| int sa, sb, size; |
| 247 |
|
| |
| 248 |
|
| /* positions inside a literal carry an offset, so size by the longest */ |
| 249 |
50 |
▶ | for (i = 0; i < a->n; i++) if (a->tok[i].len + 1 > maxa) maxa = a->tok[i].len + 1; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < a->n; i++) if (a->tok[i].len + 1 > maxa) maxa = a->tok[i].len + 1; |
18 |
18 |
36 |
| for (i = 0; i < a->n; i++) if (a->tok[i].len + 1 > maxa) maxa = a->tok[i].len + 1; |
36 |
14 |
50 |
|
| 250 |
49 |
▶ | for (i = 0; i < b->n; i++) if (b->tok[i].len + 1 > maxb) maxb = b->tok[i].len + 1; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < b->n; i++) if (b->tok[i].len + 1 > maxb) maxb = b->tok[i].len + 1; |
15 |
20 |
35 |
| for (i = 0; i < b->n; i++) if (b->tok[i].len + 1 > maxb) maxb = b->tok[i].len + 1; |
35 |
14 |
49 |
|
| 251 |
14 |
| sa = wa * (int)maxa; |
| 252 |
14 |
| sb = wb * (int)maxb; |
| 253 |
14 |
| size = sa * sb; |
| 254 |
|
| |
| 255 |
14 |
| Zero(alpha, 256, char); |
| 256 |
|
| { |
| 257 |
|
| char present[256]; |
| 258 |
14 |
| Zero(present, 256, char); |
| 259 |
50 |
▶ | for (i = 0; i < a->n; i++) if (!a->tok[i].is_var) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < a->n; i++) if (!a->tok[i].is_var) { |
20 |
16 |
36 |
| for (i = 0; i < a->n; i++) if (!a->tok[i].is_var) { |
36 |
14 |
50 |
|
| 260 |
|
| STRLEN j; |
| 261 |
145 |
▶ | for (j = 0; j < a->tok[i].len; j++) present[(U8)a->tok[i].text[j]] = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < a->tok[i].len; j++) present[(U8)a->tok[i].text[j]] = 1; |
125 |
20 |
145 |
|
| 262 |
|
| } |
| 263 |
49 |
▶ | for (i = 0; i < b->n; i++) if (!b->tok[i].is_var) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < b->n; i++) if (!b->tok[i].is_var) { |
19 |
16 |
35 |
| for (i = 0; i < b->n; i++) if (!b->tok[i].is_var) { |
35 |
14 |
49 |
|
| 264 |
|
| STRLEN j; |
| 265 |
131 |
▶ | for (j = 0; j < b->tok[i].len; j++) present[(U8)b->tok[i].text[j]] = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < b->tok[i].len; j++) present[(U8)b->tok[i].text[j]] = 1; |
112 |
19 |
131 |
|
| 266 |
|
| } |
| 267 |
3584 |
▶ | for (c = 1; c < 256; c++) if (present[c]) alpha[na++] = (char)c; |
Branch: 2 branches
| Branch | True | False | Total |
| for (c = 1; c < 256; c++) if (present[c]) alpha[na++] = (char)c; |
127 |
3443 |
3570 |
| for (c = 1; c < 256; c++) if (present[c]) alpha[na++] = (char)c; |
3570 |
14 |
3584 |
|
| 268 |
25 |
▶ | for (c = 'a'; c < 256; c++) /* one character in neither */ |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 'a'; c < 256; c++) /* one character in neither */ |
25 |
0 |
25 |
|
| 269 |
25 |
▶ | if (!present[c] && pmcp_var_char_ok((char)c)) { alpha[na++] = (char)c; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!present[c] && pmcp_var_char_ok((char)c)) { alpha[na++] = (char)c; break; } |
14 |
11 |
25 |
| if (!present[c] && pmcp_var_char_ok((char)c)) { alpha[na++] = (char)c; break; } |
14 |
0 |
14 |
|
| 270 |
|
| } |
| 271 |
|
| |
| 272 |
14 |
| Newxz(seen, size, char); |
| 273 |
14 |
| Newx(queue, size * 4, int); |
| 274 |
|
| #define PMCP_IDX(pa, pb) (((pa).k * (int)maxa + (pa).in) * sb + (pb).k * (int)maxb + (pb).in) |
| 275 |
|
| { |
| 276 |
14 |
| pmcp_pos s0 = { 0, 0 }, ca[2], cb[2]; |
| 277 |
14 |
| int x, y, nca = pmcp_close(a, s0, ca), ncb = pmcp_close(b, s0, cb); |
| 278 |
42 |
▶ | for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
14 |
14 |
28 |
| for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
14 |
14 |
28 |
|
| 279 |
14 |
| int id = PMCP_IDX(ca[x], cb[y]); |
| 280 |
14 |
▶ | if (!seen[id]) { seen[id] = 1; queue[qt++] = id; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!seen[id]) { seen[id] = 1; queue[qt++] = id; } |
14 |
0 |
14 |
|
| 281 |
|
| } |
| 282 |
|
| } |
| 283 |
125 |
▶ | while (qh < qt && !found) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (qh < qt && !found) { |
115 |
10 |
125 |
| while (qh < qt && !found) { |
115 |
0 |
115 |
|
| 284 |
115 |
| int id = queue[qh++], ci; |
| 285 |
|
| pmcp_pos pa, pb; |
| 286 |
115 |
| pa.k = (id / sb) / (int)maxa; pa.in = (id / sb) % (int)maxa; |
| 287 |
115 |
| pb.k = (id % sb) / (int)maxb; pb.in = (id % sb) % (int)maxb; |
| 288 |
115 |
▶ | if (pa.k == a->n && pb.k == b->n) { found = 1; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (pa.k == a->n && pb.k == b->n) { found = 1; break; } |
16 |
99 |
115 |
| if (pa.k == a->n && pb.k == b->n) { found = 1; break; } |
4 |
12 |
16 |
|
| 289 |
1101 |
▶ | for (ci = 0; ci < na; ci++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (ci = 0; ci < na; ci++) { |
990 |
111 |
1101 |
|
| 290 |
|
| pmcp_pos sa1[1], sb1[1], ca[2], cb[2]; |
| 291 |
|
| int x, y, nca, ncb; |
| 292 |
990 |
▶ | if (!pmcp_step(a, pa, alpha[ci], sa1) || !pmcp_step(b, pb, alpha[ci], sb1)) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!pmcp_step(a, pa, alpha[ci], sa1) || !pmcp_step(b, pb, alpha[ci], sb1)) |
288 |
702 |
990 |
| if (!pmcp_step(a, pa, alpha[ci], sa1) || !pmcp_step(b, pb, alpha[ci], sb1)) |
151 |
137 |
288 |
|
| 293 |
853 |
| continue; |
| 294 |
137 |
| nca = pmcp_close(a, sa1[0], ca); |
| 295 |
137 |
| ncb = pmcp_close(b, sb1[0], cb); |
| 296 |
773 |
▶ | for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
407 |
229 |
636 |
| for (x = 0; x < nca; x++) for (y = 0; y < ncb; y++) { |
229 |
137 |
366 |
|
| 297 |
407 |
| int nid = PMCP_IDX(ca[x], cb[y]); |
| 298 |
407 |
▶ | if (!seen[nid] && qt < size * 4) { seen[nid] = 1; queue[qt++] = nid; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!seen[nid] && qt < size * 4) { seen[nid] = 1; queue[qt++] = nid; } |
101 |
306 |
407 |
| if (!seen[nid] && qt < size * 4) { seen[nid] = 1; queue[qt++] = nid; } |
101 |
0 |
101 |
|
| 299 |
|
| } |
| 300 |
|
| } |
| 301 |
|
| } |
| 302 |
|
| #undef PMCP_IDX |
| 303 |
14 |
| Safefree(seen); |
| 304 |
14 |
| Safefree(queue); |
| 305 |
14 |
| return found; |
| 306 |
|
| } |
| 307 |
|
| |
| 308 |
|
| /* ---- base64 (standard, padded) for a blob ------------------------------------ */ |
| 309 |
|
| |
| 310 |
2 |
| static SV *pmcp_b64(pTHX_ const unsigned char *in, STRLEN n) |
| 311 |
|
| { |
| 312 |
|
| static const char tbl[] = |
| 313 |
|
| "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; |
| 314 |
2 |
| SV *out = newSV(((n + 2) / 3) * 4 + 1); |
| 315 |
2 |
| char *o = SvPVX(out); |
| 316 |
2 |
| STRLEN i = 0, k = 0; |
| 317 |
6 |
▶ | while (i + 3 <= n) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (i + 3 <= n) { |
4 |
2 |
6 |
|
| 318 |
4 |
| U32 v = ((U32)in[i] << 16) | ((U32)in[i + 1] << 8) | in[i + 2]; |
| 319 |
4 |
| o[k++] = tbl[(v >> 18) & 63]; o[k++] = tbl[(v >> 12) & 63]; |
| 320 |
4 |
| o[k++] = tbl[(v >> 6) & 63]; o[k++] = tbl[v & 63]; |
| 321 |
4 |
| i += 3; |
| 322 |
|
| } |
| 323 |
2 |
▶ | if (n - i == 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n - i == 1) { |
2 |
0 |
2 |
|
| 324 |
2 |
| U32 v = (U32)in[i] << 16; |
| 325 |
2 |
| o[k++] = tbl[(v >> 18) & 63]; o[k++] = tbl[(v >> 12) & 63]; |
| 326 |
2 |
| o[k++] = '='; o[k++] = '='; |
| 327 |
|
| } |
| 328 |
0 |
▶ | else if (n - i == 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| else if (n - i == 2) { |
0 |
0 |
0 |
|
| 329 |
0 |
| U32 v = ((U32)in[i] << 16) | ((U32)in[i + 1] << 8); |
| 330 |
0 |
| o[k++] = tbl[(v >> 18) & 63]; o[k++] = tbl[(v >> 12) & 63]; |
| 331 |
0 |
| o[k++] = tbl[(v >> 6) & 63]; o[k++] = '='; |
| 332 |
|
| } |
| 333 |
2 |
| o[k] = '\0'; |
| 334 |
2 |
| SvPOK_on(out); |
| 335 |
2 |
| SvCUR_set(out, k); |
| 336 |
2 |
| return out; |
| 337 |
|
| } |
| 338 |
|
| |
| 339 |
|
| #endif /* PMCP_URI_H */ |