что у parser внутри #2

Александр Петросян (PAF) 29.11.2005 13:16

внутри Parser строка хранится в виде двух деревьев:
листочками первого дерева являются кусочки строк,
листочками второго: их tainting.

для удобства tainting внутри обозначается и хранится буковками:
T << неопределённо tainted (только что считался из базы данных)
H << был просто tainted, но его напечатали в результат и готовы отправить посетителю
Q << был просто tainted, но напечатали в sql -запрос и готовы отправить на sql-сервер.

строку можно представить себе так:

это написано программистом, а это получено от пользователя. и опять программист.
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCTTTTTTTTTTTTTTTTTTTTTTTTTTTTCCCCCCCCCCCCCCCCCCCCCC

это только общая идея.
дальше идут оптимизации простых случаев,
оптимизации подстрок и другие интересные вещи.
http://www.parser.ru/docs/src/classString.htm#s20
http://www.parser.ru/docs/src/pa__string_8h-source.htm#l00077
http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/cordh.txt

кое-что отлаживал в ^cache, вот кусочек журнала (дерево букв)…

CORDdump
Concatenation: 0x81bf9a8 (left_len: 3, len: 10340, depth: 29)
  0x81d0570: |||!
  Concatenation: 0x81dec30 (left_len: 0, len: 10337, depth: 28)
    Concatenation: 0x81dec60 (left_len: 4, len: 10336, depth: 27)
      0x8579f90: |@|@!
      Concatenation: 0x85f4600 (left_len: 0, len: 10332, depth: 26)
        Concatenation: 0x85f4630 (left_len: 3, len: 10329, depth: 25)
          0x8579f28: @@|!
          Concatenation: 0x85fafc0 (left_len: 0, len: 10326, depth: 24)
            Concatenation: 0x85f5000 (left_len: 13, len: 10313, depth: 23)
              0x81a74a0: |<theatres>|@!
              Concatenation: 0x85f5030 (left_len: 0, len: 10300, depth: 22)
                Concatenation: 0x85f50c0 (left_len: 0, len: 10294, depth: 21)
                  Concatenation: 0x85f5228 (left_len: 0, len: 10279, depth: 20)
                    Concatenation: 0x85f5390 (left_len: 0, len: 10264, depth: 19)
                      Concatenation: 0x85f54f8 (left_len: 0, len: 10249, depth: 18)
                        Concatenation: 0x85f5660 (left_len: 0, len: 10234, depth: 17)
                          Concatenation: 0x85e89f0 (left_len: 0, len: 1817, depth: 16)
                            Concatenation: 0x85e8ac8 (left_len: 0, len: 1808, depth: 15)
                              Concatenation: 0x85e8c30 (left_len: 0, len: 1793, depth: 14)
                                Concatenation: 0x85e8d98 (left_len: 0, len: 1778, depth: 13)
                                  Concatenation: 0x85e8f00 (left_len: 0, len: 1763, depth: 12)
                                    Concatenation: 0x85e5078 (left_len: 0, len: 1748, depth: 11)
                                      Concatenation: 0x85e51e0 (left_len: 0, len: 1733, depth: 10)
                                        Concatenation: 0x85e5348 (left_len: 0, len: 1718, depth: 9)
                                          Concatenation: 0x85e54b0 (left_len: 0, len: 1703, depth: 8)
                                            Concatenation: 0x85e5618 (left_len: 0, len: 1688, depth: 7)
                                              Concatenation: 0x85e5780 (left_len: 0, len: 1673, depth: 6)
                                                Concatenation: 0x85e58e8 (left_len: 24, len: 1658, depth: 5)
                                                  Concatenation: 0x85e0078 (left_len: 15, len: 24, depth: 1)
                                                    0x854fdf8: ||@||@||@||@||@!
                                                    0x85af0c0: ||@||@||@!
                                                  Concatenation: 0x85e5bb8 (left_len: 0, len: 1634, depth: 4)
                                                    Concatenation: 0x85e5be8 (left_len: 1, len: 1632, depth: 3)
                                                      0x81d0de8: |!
                                                      Concatenation: 0x85e5c18 (left_len: 0, len: 1631, depth: 2)
                                                        Concatenation: 0x85e5c48 (left_len: 1, len: 1630, depth: 1)
                                                          0x81d0dc8: |!
                                                          0x85e324b: ||@@<theatre id="9" priority="9">|@@@|@@@|@<events label="март 2005">|@@|@@@|@@@|@@@@<event day="13" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57755">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="14" week-day="понедельник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57756">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="15" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57757">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="16" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57752">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="19" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="58352">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="21" week-day="понедельник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57753">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="0">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="24" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57754">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="26" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="58353">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@|@</events>||@@|@@|@@</theatre>|!
                                                        0x81d0ce8: |!
                                                    0x81d0ce0: |@!
                                                0x854fcd8: ||@||@||@||@||@!
                                              0x854fca8: ||@||@||@||@||@!
                                            0x854fc78: ||@||@||@||@||@!
                                          0x854fc48: ||@||@||@||@||@!
                                        0x854fc18: ||@||@||@||@||@!
                                      0x854fbe8: ||@||@||@||@||@!
                                    0x854fbb8: ||@||@||@||@||@!
                                  0x854fb88: ||@||@||@||@||@!
                                0x854fb58: ||@||@||@||@||@!
                              0x854fb28: ||@||@||@||@||@!
                            0x85e4960: ||@||@||@!
                          Concatenation: 0x85f5690 (left_len: 0, len: 8417, depth: 4)
                            Concatenation: 0x85f56c0 (left_len: 1, len: 8415, depth: 3)
                              0x81d0de8: |!
                              Concatenation: 0x85f56f0 (left_len: 0, len: 8414, depth: 2)
                                Concatenation: 0x85f5720 (left_len: 1, len: 8413, depth: 1)
                                  0x81d0dc8: |!
                                  0x85ebb6f: ||@@<theatre id="10" priority="10">|@@@|@@@|@<events label="март 2005">|@@|@@@|@@@|@@@@<event day="1" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57685">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="3" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57670">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="5" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57671">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="7" week-day="понедельник" hollyday="0" time="12:00:00" is-tickets="0" artbilet="57662">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="7" week-day="понедельник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57655">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="7" week-day="понедельник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57653">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="8" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57665">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="8" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57654">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="9" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57683">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="10" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57684">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="11" week-day="пятница" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57656">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="12" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57666">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="12" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57659">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="13" week-day="воскресение" hollyday="1" time="12:00:00" is-tickets="0" artbilet="57660">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="13" week-day="воскресение" hollyday="1" time="12:00:00" is-tickets="0" artbilet="57687">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="13" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57676">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="13" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57657">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="15" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57663">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="16" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57678">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="17" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57686">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="17" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57677">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="18" week-day="пятница" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57679">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="19" week-day="суббота" hollyday="1" time="12:00:00" is-tickets="0" artbilet="57688">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="19" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57672">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="20" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57667">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="22" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57668">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="23" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57680">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="23" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57689">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="24" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57673">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="24" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="55531">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="25" week-day="пятница" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57681">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="25" week-day="пятница" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57690">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="26" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57658">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="26" week-day="суббота" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57692">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="27" week-day="воскресение" hollyday="1" time="12:00:00" is-tickets="0" artbilet="57664">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="27" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57691">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="27" week-day="воскресение" hollyday="1" time="19:00:00" is-tickets="0" artbilet="57682">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="29" week-day="вторник" hollyday="0" time="12:00:00" is-tickets="0" artbilet="57661">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="29" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57694">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="29" week-day="вторник" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57669">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="30" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57674">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="30" week-day="среда" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57695">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="31" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57693">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@@@<event day="31" week-day="четверг" hollyday="0" time="19:00:00" is-tickets="0" artbilet="57675">|@@@@@|@@@@@@|@@@@@@|@@@@@@|@@@@@@<place own="1">|@@@@@@</place>|@@@@@|@@@@</event>|@@@|@@|@</events>||@@|@@|@@</theatre>|!
                                0x81d0ce8: |!
                            0x81d0ce0: |@!
                        0x854f6c0: ||@||@||@||@||@!
                      0x854f690: ||@||@||@||@||@!
                    0x854f660: ||@||@||@||@||@!
                  0x854f630: ||@||@||@||@||@!
                0x85ea918: ||@||@!
            0x81a73d0: |</theatres>|!
        0x81d0c58: |@@!
    0x81786f0: |!

---