Digs - Персональная территория

Авторский проект Артема Глазкова
? 
        Версия для печати (цвет)  

Delphi
» Потоки (Threads)
» Создаем ComboBox
» Создаем ComboBox-2
» Перегрузка TCustomForm.Loaded
» Поиск строковых литералов
» Continue

Использование материалов
Заметка #25
23 июня 2007

Поиск строковых литералов


    Требуется в исходном тексте на Delphi (*.pas) найти все строковые литералы. Единственное, про что нужно помнить, это про три типа комментариев. Комментарий это блок. Строковый литерал это блок. Т.е. вся задача сводится к тому, чтобы найти ближайший от текущей позиции поиска блок и затем найти его конец. При этом указатель считывания перевести в конец блока и так продолжать до конца файла (потока, строки и т.д.) запоминая где-то все строковые литералы. Так как такая операция часто предшествует операции замены, то будем также запоминать смещения начала и конца литерала в файле. Хотя это уже мелочи.
    Естественно, речь пойдет об оптимизации. Т.е. о наиболее оптимальном в плане скорости способе нахождения. Анализировать будем не последовательность строк (TStrings), а весь файл как одну строку. Для этого будем использовать PChar, как способ «навигации» по строке. Это удобно, так как Delphi позволяет добавлять к PChar-ссылкам целочисленные значения, тем самым, смещая ссылку в нужном направлении.
    Три типа комментариев и строковый литерал. Зададим массивы с символами начала и конца каждого блока:

const
  starts: array[1..4] of PChar=('(*','{','//','''');
  ends: array[1..4] of PChar=('*)','}',#13#10,'''');

    PChar это ссылка на null-terminated строку, для поиска в которой будем использовать функцию StrPos. В функцию будет подавать обычную строку, а для навигации по строке объявим переменную P.

var
  P: PChar;

    Для нахождения ближайшего блока предлагается следующий алгоритм. Сначала находим позицию первого символа некоторого блока, а затем начало следующего блока ищем до найденного символа. Чтобы это стало возможным, будем найденный символ временно заменять на ноль. Ссылку на найденный символ следует хранить, пока она актуальна, чтобы не производить новый ненужный поиск. Для этого объявляем переменную cramps.

var
  cramps: array[1..4] of PChar;

    Начинаем с цикла до конца строки, не забыв установить cramps в nil.

P := PChar(S);
UpFind := 1;
for i:=1 to 4 do cramps[i] := nil;
while P[0]<>#0 do
  begin
    ....
  end;

    Здесь переменная S (string) содержит строку, в которой производится поиск. Переменная UpFind будет определять номер блока, с которого имеет смысл делать поиск. Если при поиске самого первого блока ((*) функция StrPos вернула значение nil, то в дальнейшем, поиск этого блока производить не будем. В этом случае увеличиваем значение переменной на единицу. Поиск ближайшего блока выглядит так:

State := 0;
for i:=UpFind to 4 do
  begin
    //если блок еще не найден, то ищем его начало
    if cramps[i]=nil then cramps[i] := StrPos(P,starts[i]);
    if cramps[i]<>nil then
      begin
        State := i;
        //литерал это последний блок, поэтому замену не делаем
        if i<>4 then cramps[i][0] := #0;
      end
    else if UpFind=i then inc(UpFind);
  end;

    Переменная State хранит номер найденного блока. По завершению цикла она будет содержать номер блока, ближайшего к началу строки. После того, как все символы найдены, можно их восстановить:

for i:=UpFind to 3 do
  if cramps[i]<>nil then cramps[i][0] := starts[i][0];

    Теперь осталось проанализировать переменную State. Во-первых, если она равна нулю, то мы не нашли ни одного блока и следовательно поиск закончен. Во-вторых, анализ конца блока для всех комментариев един, поэтому объединяем их:

case State of
  0: break; //прерываем основной цикл по строке
  1..3 :
    begin
      //смещаем указатель после символа начала блока
      P := cramps[State] + Length(starts[State]);
      //ищем символ окончания блока
      temp := StrPos(P,ends[State]);
      if temp<>nil
        //если нашли, то перемещаем указатель за блок
        then P := temp+Length(ends[State])
        //иначе его забыли закрыть и он до конца файла
        else break;
    end;
...
end;

    Поиск конца литерала не расписываю. Скажу только, что он может заканчиваться не только символом конца литерала, но и символом конца строки, если его забыли поставить. Также следует помнить про двойные апострофы, которые должны преобразовываться к одинарным.
    Последним штрихом, завершающим цикл, является проверка актуальности найденного блока. Неактуальным он может быть в том случае, если был найден внутри другого блока и, начиная с некоторого момента, указатель его «обогнал». В этом случае нужно указатель сбросить в nil, чтобы выполнился новый поиск.

for i:=UpFind to 4 do
  if (cramps[i]<>nil)and(cramps[i]<P) then cramps[i] := nil;

    Собственно, для себя я на этом и успокоился, так как операция рассчитывалась как разовая, и особой прыти от нее не требовалось. Но раз уж обещал говорить про оптимизацию, расскажу, что дальше с этим делать.
    Null-terminated строки имеют один большой недостаток: длина строки нигде не хранится и потому перед каждой операцией ее приходится заново вычислять. Если строка длинная, то это становится заметным. А у нас она длинная, так как содержит целый pas-файл.
    Функция StrPos не является исключением. Нахождение завершающего нуля происходит командой scasb. Той же командой происходит поиск первого символа искомой строки. Так как сканирование во втором случае ведется максимум до завершающего нуля, то в большинстве случаев нахождение длины строки занимает больше половины времени, от всего времени работы функции.
    Если приглядеться внимательнее к функции поиска строковых литералов, то мы всегда можем сами найти длину строки. Причем, так как указатель P у нас всегда перемещается, то для вычисления достаточно будет запомнить в переменной адрес нулевого символа в конце строки. Длина всей строки будет вычисляться как разница между позицией нуля и текущим указателем. Если же мы нашли начало какого-то блока и следующий поиск делается до найденной позиции, то длина будет равна разнице между найденной позицией и текущим указателем P.
    Для того чтобы использовать вычисленную длину, нужно написать аналог функции StrPos, которая будет получать длину строки через параметр. Даже при среднем знании ассемблера написать такую функцию не составит труда. Достаточно посмотреть на исходный текст StrPos.
    Если у нас будет функция, которой мы сами будем задавать максимальную длину сканирования, то временную замену символа начала блока на ноль можно не делать. Тем самым уменьшаем код, увеличивая его наглядность.
    В заключении хочется еще сказать про сохранение позиций начала и конца строки. Частенько бывают случаи, когда большой строковый литерал записывают несколькими литералами (по одному на строку) скрепляя их знаком «+». Если вся операция задумывалась для замены литералов, например, их идентификаторами с занесением строк в словарь, то наличие знака «+» достаточно просто проанализировать. Нужно взять подстроку от позиции конца литерала до позиции начала следующего литерала, выбросить все пробелы, символы табуляции и символы перевода строк и проверить оставшееся на равенство строке «+».


© 2005-16, Powered By Digs (Написать письмо, vk)