Source/WebCore/contentextensions/Term.h

   1 /*
   2  * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef Term_h
  27 #define Term_h
  28
  29 #if ENABLE(CONTENT_EXTENSIONS)
  30
  31 #include "ContentExtensionsDebugging.h"
  32 #include "NFA.h"
  33 #include <unicode/utypes.h>
  34 #include <wtf/ASCIICType.h>
  35 #include <wtf/HashMap.h>
  36 #include <wtf/Vector.h>
  37 #include <wtf/text/StringBuilder.h>
  38 #include <wtf/text/WTFString.h>
  39
  40 namespace WebCore {
  41
  42 namespace ContentExtensions {
  43
  44 enum class AtomQuantifier : uint8_t {
  45     One,
  46     ZeroOrOne,
  47     ZeroOrMore,
  48     OneOrMore
  49 };
  50
  51 class Term {
  52 public:
  53     Term();
  54     Term(char character, bool isCaseSensitive);
  55
  56     enum UniversalTransitionTag { UniversalTransition };
  57     explicit Term(UniversalTransitionTag);
  58
  59     enum CharacterSetTermTag { CharacterSetTerm };
  60     explicit Term(CharacterSetTermTag, bool isInverted);
  61
  62     enum GroupTermTag { GroupTerm };
  63     explicit Term(GroupTermTag);
  64
  65     enum EndOfLineAssertionTermTag { EndOfLineAssertionTerm };
  66     explicit Term(EndOfLineAssertionTermTag);
  67
  68     Term(const Term& other);
  69     Term(Term&& other);
  70
  71     enum EmptyValueTag { EmptyValue };
  72     Term(EmptyValueTag);
  73
  74     enum DeletedValueTag { DeletedValue };
  75     Term(DeletedValueTag);
  76
  77     ~Term();
  78
  79     bool isValid() const;
  80
  81     // CharacterSet terms only.
  82     void addCharacter(UChar character, bool isCaseSensitive);
  83
  84     // Group terms only.
  85     void extendGroupSubpattern(const Term&);
  86
  87     void quantify(const AtomQuantifier&);
  88
  89     unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
  90
  91     bool isEndOfLineAssertion() const;
  92
  93     bool matchesAtLeastOneCharacter() const;
  94
  95     // Matches any string, the empty string included.
  96     // This is very conservative. Patterns matching any string can return false here.
  97     bool isKnownToMatchAnyString() const;
  98
  99     // Return true if the term can only match input of a single fixed length.
 100     bool hasFixedLength() const;
 101
 102     Term& operator=(const Term& other);
 103     Term& operator=(Term&& other);
 104
 105     bool operator==(const Term& other) const;
 106
 107     unsigned hash() const;
 108
 109     bool isEmptyValue() const;
 110     bool isDeletedValue() const;
 111
 112 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
 113     String toString() const;
 114 #endif
 115
 116 private:
 117     // This is exact for character sets but conservative for groups.
 118     // The return value can be false for a group equivalent to a universal transition.
 119     bool isUniversalTransition() const;
 120
 121     unsigned generateSubgraphForAtom(NFA&, unsigned source) const;
 122
 123     void destroy();
 124
 125     enum class TermType : uint8_t {
 126         Empty,
 127         Deleted,
 128         CharacterSet,
 129         Group
 130     };
 131
 132     TermType m_termType { TermType::Empty };
 133     AtomQuantifier m_quantifier { AtomQuantifier::One };
 134
 135     class CharacterSet {
 136     public:
 137         void set(UChar character)
 138         {
 139             RELEASE_ASSERT(character < 128);
 140             m_characters[character / 64] |= (uint64_t(1) << (character % 64));
 141         }
 142
 143         bool get(UChar character) const
 144         {
 145             RELEASE_ASSERT(character < 128);
 146             return m_characters[character / 64] & (uint64_t(1) << (character % 64));
 147         }
 148
 149         void invert()
 150         {
 151             ASSERT(!m_inverted);
 152             m_inverted = true;
 153         }
 154
 155         bool inverted() const { return m_inverted; }
 156
 157         unsigned bitCount() const
 158         {
 159             return WTF::bitCount(m_characters[0]) + WTF::bitCount(m_characters[1]);
 160         }
 161
 162         bool operator==(const CharacterSet& other) const
 163         {
 164             return other.m_inverted == m_inverted
 165                 && other.m_characters[0] == m_characters[0]
 166                 && other.m_characters[1] == m_characters[1];
 167         }
 168
 169         unsigned hash() const
 170         {
 171             return WTF::pairIntHash(WTF::pairIntHash(WTF::intHash(m_characters[0]), WTF::intHash(m_characters[1])), m_inverted);
 172         }
 173     private:
 174         bool m_inverted { false };
 175         uint64_t m_characters[2] { 0, 0 };
 176     };
 177
 178     struct Group {
 179         Vector<Term> terms;
 180
 181         bool operator==(const Group& other) const
 182         {
 183             return other.terms == terms;
 184         }
 185
 186         unsigned hash() const
 187         {
 188             unsigned hash = 6421749;
 189             for (const Term& term : terms) {
 190                 unsigned termHash = term.hash();
 191                 hash = (hash << 16) ^ ((termHash << 11) ^ hash);
 192                 hash += hash >> 11;
 193             }
 194             return hash;
 195         }
 196     };
 197
 198     union AtomData {
 199         AtomData()
 200             : invalidTerm(0)
 201         {
 202         }
 203         ~AtomData()
 204         {
 205         }
 206
 207         char invalidTerm;
 208         CharacterSet characterSet;
 209         Group group;
 210     } m_atomData;
 211 };
 212
 213 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
 214 inline String quantifierToString(AtomQuantifier quantifier)
 215 {
 216     switch (quantifier) {
 217     case AtomQuantifier::One:
 218         return "";
 219     case AtomQuantifier::ZeroOrOne:
 220         return "?";
 221     case AtomQuantifier::ZeroOrMore:
 222         return "*";
 223     case AtomQuantifier::OneOrMore:
 224         return "+";
 225     }
 226 }
 227
 228 inline String Term::toString() const
 229 {
 230     switch (m_termType) {
 231     case TermType::Empty:
 232         return "(Empty)";
 233     case TermType::Deleted:
 234         return "(Deleted)";
 235     case TermType::CharacterSet: {
 236         StringBuilder builder;
 237         builder.append('[');
 238         for (UChar c = 0; c < 128; c++) {
 239             if (m_atomData.characterSet.get(c)) {
 240                 if (isASCIIPrintable(c) && !isASCIISpace(c))
 241                     builder.append(c);
 242                 else {
 243                     builder.append('\\');
 244                     builder.append('u');
 245                     builder.appendNumber(c);
 246                 }
 247             }
 248         }
 249         builder.append(']');
 250         builder.append(quantifierToString(m_quantifier));
 251         return builder.toString();
 252     }
 253     case TermType::Group: {
 254         StringBuilder builder;
 255         builder.append('(');
 256         for (const Term& term : m_atomData.group.terms)
 257             builder.append(term.toString());
 258         builder.append(')');
 259         builder.append(quantifierToString(m_quantifier));
 260         return builder.toString();
 261     }
 262     }
 263 }
 264 #endif
 265
 266 struct TermHash {
 267     static unsigned hash(const Term& term) { return term.hash(); }
 268     static bool equal(const Term& a, const Term& b) { return a == b; }
 269     static const bool safeToCompareToEmptyOrDeleted = true;
 270 };
 271
 272 struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
 273
 274 inline Term::Term()
 275 {
 276 }
 277
 278 inline Term::Term(char character, bool isCaseSensitive)
 279     : m_termType(TermType::CharacterSet)
 280 {
 281     new (NotNull, &m_atomData.characterSet) CharacterSet();
 282     addCharacter(character, isCaseSensitive);
 283 }
 284
 285 inline Term::Term(UniversalTransitionTag)
 286     : m_termType(TermType::CharacterSet)
 287 {
 288     new (NotNull, &m_atomData.characterSet) CharacterSet();
 289     for (UChar i = 0; i < 128; ++i)
 290         m_atomData.characterSet.set(i);
 291 }
 292
 293 inline Term::Term(CharacterSetTermTag, bool isInverted)
 294     : m_termType(TermType::CharacterSet)
 295 {
 296     new (NotNull, &m_atomData.characterSet) CharacterSet();
 297     if (isInverted)
 298         m_atomData.characterSet.invert();
 299 }
 300
 301 inline Term::Term(GroupTermTag)
 302     : m_termType(TermType::Group)
 303 {
 304     new (NotNull, &m_atomData.group) Group();
 305 }
 306
 307 inline Term::Term(EndOfLineAssertionTermTag)
 308     : Term(CharacterSetTerm, false)
 309 {
 310     m_atomData.characterSet.set(0);
 311 }
 312
 313 inline Term::Term(const Term& other)
 314     : m_termType(other.m_termType)
 315     , m_quantifier(other.m_quantifier)
 316 {
 317     switch (m_termType) {
 318     case TermType::Empty:
 319     case TermType::Deleted:
 320         break;
 321     case TermType::CharacterSet:
 322         new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
 323         break;
 324     case TermType::Group:
 325         new (NotNull, &m_atomData.group) Group(other.m_atomData.group);
 326         break;
 327     }
 328 }
 329
 330 inline Term::Term(Term&& other)
 331     : m_termType(WTF::move(other.m_termType))
 332     , m_quantifier(WTF::move(other.m_quantifier))
 333 {
 334     switch (m_termType) {
 335     case TermType::Empty:
 336     case TermType::Deleted:
 337         break;
 338     case TermType::CharacterSet:
 339         new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
 340         break;
 341     case TermType::Group:
 342         new (NotNull, &m_atomData.group) Group(WTF::move(other.m_atomData.group));
 343         break;
 344     }
 345     other.destroy();
 346 }
 347
 348 inline Term::Term(EmptyValueTag)
 349     : m_termType(TermType::Empty)
 350 {
 351 }
 352
 353 inline Term::Term(DeletedValueTag)
 354     : m_termType(TermType::Deleted)
 355 {
 356 }
 357
 358 inline Term::~Term()
 359 {
 360     destroy();
 361 }
 362
 363 inline bool Term::isValid() const
 364 {
 365     return m_termType != TermType::Empty && m_termType != TermType::Deleted;
 366 }
 367
 368 inline void Term::addCharacter(UChar character, bool isCaseSensitive)
 369 {
 370     ASSERT(isASCII(character));
 371
 372     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
 373     if (m_termType != TermType::CharacterSet)
 374         return;
 375
 376     if (isCaseSensitive || !isASCIIAlpha(character))
 377         m_atomData.characterSet.set(character);
 378     else {
 379         m_atomData.characterSet.set(toASCIIUpper(character));
 380         m_atomData.characterSet.set(toASCIILower(character));
 381     }
 382 }
 383
 384 inline void Term::extendGroupSubpattern(const Term& term)
 385 {
 386     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::Group);
 387     if (m_termType != TermType::Group)
 388         return;
 389     m_atomData.group.terms.append(term);
 390 }
 391
 392 inline void Term::quantify(const AtomQuantifier& quantifier)
 393 {
 394     ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
 395     m_quantifier = quantifier;
 396 }
 397
 398 inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
 399 {
 400     ASSERT(isValid());
 401
 402     unsigned newEnd;
 403
 404     switch (m_quantifier) {
 405     case AtomQuantifier::One: {
 406         newEnd = generateSubgraphForAtom(nfa, start);
 407         break;
 408     }
 409     case AtomQuantifier::ZeroOrOne: {
 410         newEnd = generateSubgraphForAtom(nfa, start);
 411         nfa.addEpsilonTransition(start, newEnd);
 412         break;
 413     }
 414     case AtomQuantifier::ZeroOrMore: {
 415         unsigned repeatStart = nfa.createNode();
 416         nfa.addEpsilonTransition(start, repeatStart);
 417
 418         unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
 419         nfa.addEpsilonTransition(repeatEnd, repeatStart);
 420
 421         unsigned kleenEnd = nfa.createNode();
 422         nfa.addEpsilonTransition(repeatEnd, kleenEnd);
 423         nfa.addEpsilonTransition(start, kleenEnd);
 424         newEnd = kleenEnd;
 425         break;
 426     }
 427     case AtomQuantifier::OneOrMore: {
 428         unsigned repeatStart = nfa.createNode();
 429         nfa.addEpsilonTransition(start, repeatStart);
 430
 431         unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
 432         nfa.addEpsilonTransition(repeatEnd, repeatStart);
 433
 434         unsigned afterRepeat = nfa.createNode();
 435         nfa.addEpsilonTransition(repeatEnd, afterRepeat);
 436         newEnd = afterRepeat;
 437         break;
 438     }
 439     }
 440     nfa.setActions(newEnd, finalActions);
 441     return newEnd;
 442 }
 443
 444 inline bool Term::isEndOfLineAssertion() const
 445 {
 446     return m_termType == TermType::CharacterSet && m_atomData.characterSet.bitCount() == 1 && m_atomData.characterSet.get(0);
 447 }
 448
 449 inline bool Term::matchesAtLeastOneCharacter() const
 450 {
 451     ASSERT(isValid());
 452
 453     if (m_quantifier == AtomQuantifier::ZeroOrOne || m_quantifier == AtomQuantifier::ZeroOrMore)
 454         return false;
 455     if (isEndOfLineAssertion())
 456         return false;
 457
 458     if (m_termType == TermType::Group) {
 459         for (const Term& term : m_atomData.group.terms) {
 460             if (term.matchesAtLeastOneCharacter())
 461                 return true;
 462         }
 463         return false;
 464     }
 465     return true;
 466 }
 467
 468 inline bool Term::isKnownToMatchAnyString() const
 469 {
 470     ASSERT(isValid());
 471
 472     switch (m_termType) {
 473     case TermType::Empty:
 474     case TermType::Deleted:
 475         ASSERT_NOT_REACHED();
 476         break;
 477     case TermType::CharacterSet:
 478         // ".*" is the only simple term matching any string.
 479         return isUniversalTransition() && m_quantifier == AtomQuantifier::ZeroOrMore;
 480         break;
 481     case TermType::Group: {
 482         // There are infinitely many ways to match anything with groups, we just handle simple cases
 483         if (m_atomData.group.terms.size() != 1)
 484             return false;
 485
 486         const Term& firstTermInGroup = m_atomData.group.terms.first();
 487         // -(.*) with any quantifier.
 488         if (firstTermInGroup.isKnownToMatchAnyString())
 489             return true;
 490
 491         if (firstTermInGroup.isUniversalTransition()) {
 492             // -(.)*, (.+)*, (.?)* etc.
 493             if (m_quantifier == AtomQuantifier::ZeroOrMore)
 494                 return true;
 495
 496             // -(.+)?.
 497             if (m_quantifier == AtomQuantifier::ZeroOrOne && firstTermInGroup.m_quantifier == AtomQuantifier::OneOrMore)
 498                 return true;
 499
 500             // -(.?)+.
 501             if (m_quantifier == AtomQuantifier::OneOrMore && firstTermInGroup.m_quantifier == AtomQuantifier::ZeroOrOne)
 502                 return true;
 503         }
 504         break;
 505     }
 506     }
 507     return false;
 508 }
 509
 510 inline bool Term::hasFixedLength() const
 511 {
 512     ASSERT(isValid());
 513
 514     switch (m_termType) {
 515     case TermType::Empty:
 516     case TermType::Deleted:
 517         ASSERT_NOT_REACHED();
 518         break;
 519     case TermType::CharacterSet:
 520         return m_quantifier == AtomQuantifier::One;
 521     case TermType::Group: {
 522         if (m_quantifier != AtomQuantifier::One)
 523             return false;
 524         for (const Term& term : m_atomData.group.terms) {
 525             if (!term.hasFixedLength())
 526                 return false;
 527         }
 528         return true;
 529     }
 530     }
 531     return false;
 532 }
 533
 534 inline Term& Term::operator=(const Term& other)
 535 {
 536     destroy();
 537     new (NotNull, this) Term(other);
 538     return *this;
 539 }
 540
 541 inline Term& Term::operator=(Term&& other)
 542 {
 543     destroy();
 544     new (NotNull, this) Term(WTF::move(other));
 545     return *this;
 546 }
 547
 548 inline bool Term::operator==(const Term& other) const
 549 {
 550     if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
 551         return false;
 552
 553     switch (m_termType) {
 554     case TermType::Empty:
 555     case TermType::Deleted:
 556         return true;
 557     case TermType::CharacterSet:
 558         return m_atomData.characterSet == other.m_atomData.characterSet;
 559     case TermType::Group:
 560         return m_atomData.group == other.m_atomData.group;
 561     }
 562     ASSERT_NOT_REACHED();
 563     return false;
 564 }
 565
 566 inline unsigned Term::hash() const
 567 {
 568     unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
 569     unsigned secondary = 0;
 570     switch (m_termType) {
 571     case TermType::Empty:
 572         secondary = 52184393;
 573         break;
 574     case TermType::Deleted:
 575         secondary = 40342988;
 576         break;
 577     case TermType::CharacterSet:
 578         secondary = m_atomData.characterSet.hash();
 579         break;
 580     case TermType::Group:
 581         secondary = m_atomData.group.hash();
 582         break;
 583     }
 584     return WTF::pairIntHash(primary, secondary);
 585 }
 586
 587 inline bool Term::isEmptyValue() const
 588 {
 589     return m_termType == TermType::Empty;
 590 }
 591
 592 inline bool Term::isDeletedValue() const
 593 {
 594     return m_termType == TermType::Deleted;
 595 }
 596
 597 inline bool Term::isUniversalTransition() const
 598 {
 599     ASSERT(isValid());
 600
 601     switch (m_termType) {
 602     case TermType::Empty:
 603     case TermType::Deleted:
 604         ASSERT_NOT_REACHED();
 605         break;
 606     case TermType::CharacterSet:
 607         return (m_atomData.characterSet.inverted() && !m_atomData.characterSet.bitCount())
 608             || (!m_atomData.characterSet.inverted() && m_atomData.characterSet.bitCount() == 128);
 609     case TermType::Group:
 610         return m_atomData.group.terms.size() == 1 && m_atomData.group.terms.first().isUniversalTransition();
 611     }
 612     return false;
 613 }
 614
 615 inline unsigned Term::generateSubgraphForAtom(NFA& nfa, unsigned source) const
 616 {
 617     switch (m_termType) {
 618     case TermType::Empty:
 619     case TermType::Deleted:
 620         ASSERT_NOT_REACHED();
 621         return -1;
 622     case TermType::CharacterSet: {
 623         unsigned target = nfa.createNode();
 624         if (isUniversalTransition())
 625             nfa.addTransitionsOnAnyCharacter(source, target);
 626         else {
 627             if (!m_atomData.characterSet.inverted()) {
 628                 for (UChar i = 0; i < 128; ++i) {
 629                     if (m_atomData.characterSet.get(i))
 630                         nfa.addTransition(source, target, static_cast<char>(i));
 631                 }
 632             } else {
 633                 for (UChar i = 1; i < 128; ++i) {
 634                     if (!m_atomData.characterSet.get(i))
 635                         nfa.addTransition(source, target, static_cast<char>(i));
 636                 }
 637             }
 638         }
 639         return target;
 640     }
 641     case TermType::Group: {
 642         unsigned lastTarget = source;
 643         for (const Term& term : m_atomData.group.terms)
 644             lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
 645         return lastTarget;
 646     }
 647     }
 648 }
 649
 650 inline void Term::destroy()
 651 {
 652     switch (m_termType) {
 653     case TermType::Empty:
 654     case TermType::Deleted:
 655         break;
 656     case TermType::CharacterSet:
 657         m_atomData.characterSet.~CharacterSet();
 658         break;
 659     case TermType::Group:
 660         m_atomData.group.~Group();
 661         break;
 662     }
 663     m_termType = TermType::Deleted;
 664 }
 665
 666 } // namespace ContentExtensions
 667 } // namespace WebCore
 668
 669 #endif // ENABLE(CONTENT_EXTENSIONS)
 670
 671 #endif // Term_h