.github
1 year ago
.gitignore
1 year ago
.travis.yml
2 years ago
LICENSE
3 years ago
MANIFEST.in
2 years ago
README.md
1 year ago
__init__.py
1 year ago
composer.json
3 years ago
crawler-user-agents.json
1 year ago
format.js
1 year ago
go.mod
2 years ago
go.sum
2 years ago
index.d.ts
3 years ago
main.php
3 years ago
package-lock.json
2 years ago
package.json
2 years ago
pyproject.toml
1 year ago
test_harness.py
1 year ago
test_validation.py
3 years ago
validate.go
1 year ago
validate.php
3 years ago
validate.py
2 years ago
validate_test.go
1 year ago
validate.go
540 lines
| 1 | package agents |
| 2 | |
| 3 | import ( |
| 4 | _ "embed" |
| 5 | "encoding/hex" |
| 6 | "encoding/json" |
| 7 | "fmt" |
| 8 | "hash/maphash" |
| 9 | "regexp" |
| 10 | "regexp/syntax" |
| 11 | "strconv" |
| 12 | "strings" |
| 13 | "time" |
| 14 | "unicode" |
| 15 | ) |
| 16 | |
| 17 | //go:embed crawler-user-agents.json |
| 18 | var crawlersJson []byte |
| 19 | |
| 20 | // Crawler contains information about one crawler. |
| 21 | type Crawler struct { |
| 22 | // Regexp of User Agent of the crawler. |
| 23 | Pattern string `json:"pattern"` |
| 24 | |
| 25 | // Discovery date. |
| 26 | AdditionDate time.Time `json:"addition_date"` |
| 27 | |
| 28 | // Official url of the robot. |
| 29 | URL string `json:"url"` |
| 30 | |
| 31 | // Examples of full User Agent strings. |
| 32 | Instances []string ``json:"instances"` |
| 33 | } |
| 34 | |
| 35 | // Private type needed to convert addition_date from/to the format used in JSON. |
| 36 | type jsonCrawler struct { |
| 37 | Pattern string `json:"pattern"` |
| 38 | AdditionDate string `json:"addition_date"` |
| 39 | URL string `json:"url"` |
| 40 | Instances []string `json:"instances"` |
| 41 | } |
| 42 | |
| 43 | const timeLayout = "2006/01/02" |
| 44 | |
| 45 | func (c Crawler) MarshalJSON() ([]byte, error) { |
| 46 | jc := jsonCrawler{ |
| 47 | Pattern: c.Pattern, |
| 48 | AdditionDate: c.AdditionDate.Format(timeLayout), |
| 49 | URL: c.URL, |
| 50 | Instances: c.Instances, |
| 51 | } |
| 52 | return json.Marshal(jc) |
| 53 | } |
| 54 | |
| 55 | func (c *Crawler) UnmarshalJSON(b []byte) error { |
| 56 | var jc jsonCrawler |
| 57 | if err := json.Unmarshal(b, &jc); err != nil { |
| 58 | return err |
| 59 | } |
| 60 | |
| 61 | c.Pattern = jc.Pattern |
| 62 | c.URL = jc.URL |
| 63 | c.Instances = jc.Instances |
| 64 | |
| 65 | if c.Pattern == "" { |
| 66 | return fmt.Errorf("empty pattern in record %s", string(b)) |
| 67 | } |
| 68 | |
| 69 | if jc.AdditionDate != "" { |
| 70 | tim, err := time.ParseInLocation(timeLayout, jc.AdditionDate, time.UTC) |
| 71 | if err != nil { |
| 72 | return err |
| 73 | } |
| 74 | c.AdditionDate = tim |
| 75 | } |
| 76 | |
| 77 | return nil |
| 78 | } |
| 79 | |
| 80 | // The list of crawlers, built from contents of crawler-user-agents.json. |
| 81 | var Crawlers = func() []Crawler { |
| 82 | var crawlers []Crawler |
| 83 | if err := json.Unmarshal(crawlersJson, &crawlers); err != nil { |
| 84 | panic(err) |
| 85 | } |
| 86 | return crawlers |
| 87 | }() |
| 88 | |
| 89 | // analyzePattern expands a regular expression to the list of matching texts |
| 90 | // for plain search. The list is complete, i.e. iff a text matches the input |
| 91 | // pattern, then it contains at least one of the returned texts. If such a list |
| 92 | // can't be built, then the resulting list contains one element (main literal), |
| 93 | // it also returns built regexp object to run in this case. The main literal is |
| 94 | // a text that is contained in any matching text and is used to optimize search |
| 95 | // (pre-filter with this main literal before running a regexp). In the case such |
| 96 | // a main literal can't be found or the regexp is invalid, an error is returned. |
| 97 | func analyzePattern(pattern string) ([]string, *regexp.Regexp, error) { |
| 98 | re, err := syntax.Parse(pattern, syntax.Perl) |
| 99 | if err != nil { |
| 100 | return nil, nil, fmt.Errorf("re %q does not compile: %w", pattern, err) |
| 101 | } |
| 102 | re = re.Simplify() |
| 103 | |
| 104 | // Try to convert it to the list of literals. |
| 105 | const maxLiterals = 100 |
| 106 | literals, ok := literalizeRegexp(re, maxLiterals) |
| 107 | if ok { |
| 108 | return literals, nil, nil |
| 109 | } |
| 110 | |
| 111 | // Fallback to using a regexp, but we need some string serving as |
| 112 | // an indicator of its possible presence. |
| 113 | mainLiteral := findLongestCommonLiteral(re) |
| 114 | const minLiteralLen = 3 |
| 115 | if len(mainLiteral) < minLiteralLen { |
| 116 | return nil, nil, fmt.Errorf("re %q does not contain sufficiently long literal to serve an indicator. The longest literal is %q", pattern, mainLiteral) |
| 117 | } |
| 118 | |
| 119 | return []string{mainLiteral}, regexp.MustCompile(pattern), nil |
| 120 | } |
| 121 | |
| 122 | // literalizeRegexp expands a regexp to the list of matching sub-strings. |
| 123 | // Iff a text matches the regexp, it contains at least one of the returned |
| 124 | // texts. Argument maxLiterals regulates the maximum number of patterns to |
| 125 | // return. In case of an overflow or if it is impossible to build such a list |
| 126 | // from the regexp, false is returned. |
| 127 | func literalizeRegexp(re *syntax.Regexp, maxLiterals int) (literals []string, ok bool) { |
| 128 | switch re.Op { |
| 129 | case syntax.OpNoMatch: |
| 130 | return nil, true |
| 131 | |
| 132 | case syntax.OpEmptyMatch: |
| 133 | return []string{""}, true |
| 134 | |
| 135 | case syntax.OpLiteral: |
| 136 | return unwrapCase(re, []string{string(re.Rune)}, maxLiterals) |
| 137 | |
| 138 | case syntax.OpCharClass: |
| 139 | count := 0 |
| 140 | for i := 0; i < len(re.Rune); i += 2 { |
| 141 | first := re.Rune[i] |
| 142 | last := re.Rune[i+1] |
| 143 | count += int(last - first + 1) |
| 144 | } |
| 145 | |
| 146 | if count > maxLiterals { |
| 147 | return nil, false |
| 148 | } |
| 149 | |
| 150 | patterns := make([]string, 0, count) |
| 151 | for i := 0; i < len(re.Rune); i += 2 { |
| 152 | first := re.Rune[i] |
| 153 | last := re.Rune[i+1] |
| 154 | for r := first; r <= last; r++ { |
| 155 | patterns = append(patterns, string([]rune{r})) |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | return unwrapCase(re, patterns, maxLiterals) |
| 160 | |
| 161 | case syntax.OpAnyCharNotNL, syntax.OpAnyChar: |
| 162 | // Not supported. |
| 163 | return nil, false |
| 164 | |
| 165 | case syntax.OpBeginLine, syntax.OpBeginText: |
| 166 | return []string{"^"}, true |
| 167 | |
| 168 | case syntax.OpEndLine, syntax.OpEndText: |
| 169 | return []string{"$"}, true |
| 170 | |
| 171 | case syntax.OpWordBoundary, syntax.OpNoWordBoundary: |
| 172 | // Not supported. |
| 173 | return nil, false |
| 174 | |
| 175 | case syntax.OpCapture: |
| 176 | subList, ok := literalizeRegexp(re.Sub[0], maxLiterals) |
| 177 | if !ok { |
| 178 | return nil, false |
| 179 | } |
| 180 | |
| 181 | return unwrapCase(re, subList, maxLiterals) |
| 182 | |
| 183 | case syntax.OpStar, syntax.OpPlus: |
| 184 | // Not supported. |
| 185 | return nil, false |
| 186 | |
| 187 | case syntax.OpQuest: |
| 188 | if re.Flags&syntax.FoldCase != 0 { |
| 189 | return nil, false |
| 190 | } |
| 191 | |
| 192 | subList, ok := literalizeRegexp(re.Sub[0], maxLiterals) |
| 193 | if !ok { |
| 194 | return nil, false |
| 195 | } |
| 196 | subList = append(subList, "") |
| 197 | |
| 198 | return subList, true |
| 199 | |
| 200 | case syntax.OpRepeat: |
| 201 | // Not supported. |
| 202 | return nil, false |
| 203 | |
| 204 | case syntax.OpConcat: |
| 205 | if re.Flags&syntax.FoldCase != 0 { |
| 206 | return nil, false |
| 207 | } |
| 208 | |
| 209 | matrix := make([][]string, len(re.Sub)) |
| 210 | for i, sub := range re.Sub { |
| 211 | subList, ok := literalizeRegexp(sub, maxLiterals) |
| 212 | if !ok { |
| 213 | return nil, false |
| 214 | } |
| 215 | matrix[i] = subList |
| 216 | } |
| 217 | |
| 218 | return combinations(matrix, maxLiterals) |
| 219 | |
| 220 | case syntax.OpAlternate: |
| 221 | results := []string{} |
| 222 | for _, sub := range re.Sub { |
| 223 | subList, ok := literalizeRegexp(sub, maxLiterals) |
| 224 | if !ok { |
| 225 | return nil, false |
| 226 | } |
| 227 | results = append(results, subList...) |
| 228 | } |
| 229 | |
| 230 | if len(results) > maxLiterals { |
| 231 | return nil, false |
| 232 | } |
| 233 | |
| 234 | return unwrapCase(re, results, maxLiterals) |
| 235 | |
| 236 | default: |
| 237 | // Not supported. |
| 238 | return nil, false |
| 239 | } |
| 240 | } |
| 241 | |
| 242 | // combinations produces all combination of elements of matrix. |
| 243 | // Each sub-slice of matrix contributes one part of a resulting string. |
| 244 | // If the number of combinations is larger than maxLiterals, the function |
| 245 | // returns false. |
| 246 | func combinations(matrix [][]string, maxLiterals int) ([]string, bool) { |
| 247 | if len(matrix) == 1 { |
| 248 | if len(matrix[0]) > maxLiterals { |
| 249 | return nil, false |
| 250 | } |
| 251 | |
| 252 | return matrix[0], true |
| 253 | } |
| 254 | |
| 255 | prefixes := matrix[0] |
| 256 | suffixes, ok := combinations(matrix[1:], maxLiterals) |
| 257 | if !ok { |
| 258 | return nil, false |
| 259 | } |
| 260 | |
| 261 | size := len(prefixes) * len(suffixes) |
| 262 | if size > maxLiterals { |
| 263 | return nil, false |
| 264 | } |
| 265 | |
| 266 | results := make([]string, 0, size) |
| 267 | for _, prefix := range prefixes { |
| 268 | for _, suffix := range suffixes { |
| 269 | results = append(results, prefix+suffix) |
| 270 | } |
| 271 | } |
| 272 | |
| 273 | return results, true |
| 274 | } |
| 275 | |
| 276 | // unwrapCase takes the regexp and the list of patterns expanded from it and |
| 277 | // further expands it for a case-insensitive regexp, if needed. Argument |
| 278 | // maxLiterals regulates the maximum number of patterns to return. In case of an |
| 279 | // overflow, false is returned. |
| 280 | func unwrapCase(re *syntax.Regexp, patterns []string, maxLiterals int) ([]string, bool) { |
| 281 | if re.Flags&syntax.FoldCase == 0 { |
| 282 | return patterns, true |
| 283 | } |
| 284 | |
| 285 | results := []string{} |
| 286 | for _, pattern := range patterns { |
| 287 | matrix := make([][]string, len(pattern)) |
| 288 | for i, r := range pattern { |
| 289 | upper := unicode.ToUpper(r) |
| 290 | lower := unicode.ToLower(r) |
| 291 | matrix[i] = []string{ |
| 292 | string([]rune{upper}), |
| 293 | string([]rune{lower}), |
| 294 | } |
| 295 | } |
| 296 | |
| 297 | patterns, ok := combinations(matrix, maxLiterals) |
| 298 | if !ok { |
| 299 | return nil, false |
| 300 | } |
| 301 | |
| 302 | results = append(results, patterns...) |
| 303 | if len(results) > maxLiterals { |
| 304 | return nil, false |
| 305 | } |
| 306 | } |
| 307 | |
| 308 | return results, true |
| 309 | } |
| 310 | |
| 311 | // findLongestCommonLiteral finds the longest common literal in the regexp. It's |
| 312 | // such a string which is contained in any text matching the regexp. If such a |
| 313 | // literal can't be found, it returns an empty string. |
| 314 | func findLongestCommonLiteral(re *syntax.Regexp) string { |
| 315 | if re.Flags&syntax.FoldCase != 0 { |
| 316 | return "" |
| 317 | } |
| 318 | |
| 319 | switch re.Op { |
| 320 | case syntax.OpNoMatch, syntax.OpEmptyMatch: |
| 321 | return "" |
| 322 | |
| 323 | case syntax.OpLiteral: |
| 324 | return string(re.Rune) |
| 325 | |
| 326 | case syntax.OpCharClass, syntax.OpAnyCharNotNL, syntax.OpAnyChar: |
| 327 | return "" |
| 328 | |
| 329 | case syntax.OpBeginLine, syntax.OpBeginText: |
| 330 | return "^" |
| 331 | |
| 332 | case syntax.OpEndLine, syntax.OpEndText: |
| 333 | return "$" |
| 334 | |
| 335 | case syntax.OpWordBoundary, syntax.OpNoWordBoundary: |
| 336 | return "" |
| 337 | |
| 338 | case syntax.OpCapture: |
| 339 | return findLongestCommonLiteral(re.Sub[0]) |
| 340 | |
| 341 | case syntax.OpStar: |
| 342 | return "" |
| 343 | |
| 344 | case syntax.OpPlus: |
| 345 | return findLongestCommonLiteral(re.Sub[0]) |
| 346 | |
| 347 | case syntax.OpQuest: |
| 348 | return "" |
| 349 | |
| 350 | case syntax.OpRepeat: |
| 351 | if re.Min >= 1 { |
| 352 | return findLongestCommonLiteral(re.Sub[0]) |
| 353 | } |
| 354 | |
| 355 | return "" |
| 356 | |
| 357 | case syntax.OpConcat: |
| 358 | longest := "" |
| 359 | for _, sub := range re.Sub { |
| 360 | str := findLongestCommonLiteral(sub) |
| 361 | if len(str) > len(longest) { |
| 362 | longest = str |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | return longest |
| 367 | |
| 368 | case syntax.OpAlternate: |
| 369 | return "" |
| 370 | |
| 371 | default: |
| 372 | return "" |
| 373 | } |
| 374 | } |
| 375 | |
| 376 | type regexpPattern struct { |
| 377 | re *regexp.Regexp |
| 378 | index int |
| 379 | } |
| 380 | |
| 381 | type matcher struct { |
| 382 | replacer *strings.Replacer |
| 383 | regexps []regexpPattern |
| 384 | } |
| 385 | |
| 386 | var uniqueToken = hex.EncodeToString((&maphash.Hash{}).Sum(nil)) |
| 387 | |
| 388 | const ( |
| 389 | uniqueTokenLen = 2 * 8 |
| 390 | numLen = 5 |
| 391 | literalLabel = '-' |
| 392 | regexpLabel = '*' |
| 393 | ) |
| 394 | |
| 395 | var m = func() matcher { |
| 396 | if len(uniqueToken) != uniqueTokenLen { |
| 397 | panic("len(uniqueToken) != uniqueTokenLen") |
| 398 | } |
| 399 | |
| 400 | regexps := []regexpPattern{} |
| 401 | oldnew := make([]string, 0, len(Crawlers)*2) |
| 402 | |
| 403 | // Put re-based patterns to the end to prevent AdsBot-Google from |
| 404 | // shadowing AdsBot-Google-Mobile. |
| 405 | var oldnew2 []string |
| 406 | |
| 407 | for i, crawler := range Crawlers { |
| 408 | literals, re, err := analyzePattern(crawler.Pattern) |
| 409 | if err != nil { |
| 410 | panic(err) |
| 411 | } |
| 412 | |
| 413 | label := literalLabel |
| 414 | num := i |
| 415 | if re != nil { |
| 416 | label = regexpLabel |
| 417 | num = len(regexps) |
| 418 | regexps = append(regexps, regexpPattern{ |
| 419 | re: re, |
| 420 | index: i, |
| 421 | }) |
| 422 | } |
| 423 | |
| 424 | replaceWith := fmt.Sprintf(" %s%c%0*d ", uniqueToken, label, numLen, num) |
| 425 | |
| 426 | for _, literal := range literals { |
| 427 | if re != nil { |
| 428 | oldnew2 = append(oldnew2, literal, replaceWith) |
| 429 | } else { |
| 430 | oldnew = append(oldnew, literal, replaceWith) |
| 431 | } |
| 432 | } |
| 433 | } |
| 434 | oldnew = append(oldnew, oldnew2...) |
| 435 | |
| 436 | // Allocate another array with regexps of exact size to save memory. |
| 437 | regexps2 := make([]regexpPattern, len(regexps)) |
| 438 | copy(regexps2, regexps) |
| 439 | |
| 440 | r := strings.NewReplacer(oldnew...) |
| 441 | r.Replace("") // To cause internal build process. |
| 442 | |
| 443 | return matcher{ |
| 444 | replacer: r, |
| 445 | regexps: regexps2, |
| 446 | } |
| 447 | }() |
| 448 | |
| 449 | // Returns if User Agent string matches any of crawler patterns. |
| 450 | func IsCrawler(userAgent string) bool { |
| 451 | // This code is mostly copy-paste of MatchingCrawlers, |
| 452 | // but with early exit logic, so it works a but faster. |
| 453 | |
| 454 | text := "^" + userAgent + "$" |
| 455 | replaced := m.replacer.Replace(text) |
| 456 | if replaced == text { |
| 457 | return false |
| 458 | } |
| 459 | |
| 460 | for { |
| 461 | uniquePos := strings.Index(replaced, uniqueToken) |
| 462 | if uniquePos == -1 { |
| 463 | break |
| 464 | } |
| 465 | |
| 466 | start := uniquePos + uniqueTokenLen + 1 |
| 467 | if start+numLen >= len(replaced) { |
| 468 | panic("corrupt replaced: " + replaced) |
| 469 | } |
| 470 | |
| 471 | label := replaced[start-1] |
| 472 | switch label { |
| 473 | case literalLabel: |
| 474 | return true |
| 475 | case regexpLabel: |
| 476 | // Rare case. Run regexp to confirm the match. |
| 477 | indexStr := replaced[start : start+numLen] |
| 478 | index, err := strconv.Atoi(indexStr) |
| 479 | if err != nil { |
| 480 | panic("corrupt replaced: " + replaced) |
| 481 | } |
| 482 | rp := m.regexps[index] |
| 483 | if rp.re.MatchString(userAgent) { |
| 484 | return true |
| 485 | } |
| 486 | default: |
| 487 | panic("corrupt replaced: " + replaced) |
| 488 | } |
| 489 | |
| 490 | replaced = replaced[start+numLen:] |
| 491 | } |
| 492 | |
| 493 | return false |
| 494 | } |
| 495 | |
| 496 | // Finds all crawlers matching the User Agent and returns the list of their indices in Crawlers. |
| 497 | func MatchingCrawlers(userAgent string) []int { |
| 498 | text := "^" + userAgent + "$" |
| 499 | replaced := m.replacer.Replace(text) |
| 500 | if replaced == text { |
| 501 | return []int{} |
| 502 | } |
| 503 | |
| 504 | indices := []int{} |
| 505 | for { |
| 506 | uniquePos := strings.Index(replaced, uniqueToken) |
| 507 | if uniquePos == -1 { |
| 508 | break |
| 509 | } |
| 510 | |
| 511 | start := uniquePos + uniqueTokenLen + 1 |
| 512 | if start+numLen >= len(replaced) { |
| 513 | panic("corrupt replaced: " + replaced) |
| 514 | } |
| 515 | indexStr := replaced[start : start+numLen] |
| 516 | index, err := strconv.Atoi(indexStr) |
| 517 | if err != nil { |
| 518 | panic("corrupt replaced: " + replaced) |
| 519 | } |
| 520 | |
| 521 | label := replaced[start-1] |
| 522 | switch label { |
| 523 | case literalLabel: |
| 524 | indices = append(indices, index) |
| 525 | case regexpLabel: |
| 526 | // Rare case. Run regexp to confirm the match. |
| 527 | rp := m.regexps[index] |
| 528 | if rp.re.MatchString(userAgent) { |
| 529 | indices = append(indices, rp.index) |
| 530 | } |
| 531 | default: |
| 532 | panic("corrupt replaced: " + replaced) |
| 533 | } |
| 534 | |
| 535 | replaced = replaced[start+numLen:] |
| 536 | } |
| 537 | |
| 538 | return indices |
| 539 | } |
| 540 |