今日の照合ループ

昨日と大して変わってないように見えても、実は裏で大きな変更が行われた今日の MacthCore ループ。

function TREMatchEngine.MatchCore(var NFACode: TRENFACode;
  var AStr: PWideChar): Boolean;
var
  NFAStack, StrStack: TList;

  procedure CreateStack;
  begin
    NFAStack := TList.Create;
    StrStack := TList.Create;
  end;

  procedure DestroyStack;
  begin
    NFAStack.Free;
    StrStack.Free;
  end;

  procedure Push(NFACode: TRENFACode; AStr: PWideChar);
  begin
    NFAStack.Add(NFACode);
    StrStack.Add(AStr);
  end;

  procedure Pop(var NFACode: TRENFACode; var AStr: PWideChar);
  var
    Index: Integer;
  begin
    Index := NFAStack.Count - 1;
    if Index = -1 then
      Exit;
    NFACode := NFAStack[Index];
    NFAStack.Delete(Index);
    AStr := StrStack[Index];
    StrStack.Delete(Index);
  end;

  function SkipNext(NFACode: TRENFACode): TRENFACode;
  begin
    while (NFACode nil) and (NFACode.Kind in [nkEmpty, nkGroupEnd, nkStar,
      nkQuest, nkAheadNoMatch]) do
      NFACode := FStateList[NFACode.TransitTo];
    Result := NFACode;
  end;

var
  Len: Integer;
  SubCode: TRENFACode;
  SubP: PWideChar;
begin
  CreateStack;
  try
    Result := False;
    while NFACode nil do
    begin
      if NFACode.Next nil then
      begin
        case NFACode.Kind of
          nkStar:
            begin
              SubCode := FStateList[NFACode.TransitTo];
              case NFACode.MatchKind of
                lmNormal:
                  begin
                    SubCode := SkipNext(SubCode);
                    Push(SubCode, AStr);
                    NFACode := NFACode.Next;
                  end;
                lmMin:
                  begin
                    Push(SkipNext(NFACode.Next), AStr);
                    NFACode := SubCode;
                  end;
              else
                NFACode := SubCode.Next;
              end;
            end;
          nkQuest:
            begin
              case NFACode.MatchKind of
                lmNormal:
                  begin
                    SubCode := SkipNext(NFACode);
                    Push(SubCode, AStr);
                    NFACode := NFACode.Next;
                  end;
                lmMin:
                  begin
                    SubCode := SkipNext(NFACode.Next);
                    Push(SubCode, AStr);
                    NFACode := FStateList[NFACode.TransitTo];
                  end;
              else
                NFACode := NFACode.Next;
              end;
            end;
          nkAheadNoMatch:
            begin
              SubCode := SkipNext(NFACode);
              Push(SubCode, AStr);
              NFACode := NFACode.Next;
            end;
        else
          begin
            SubCode := SkipNext(NFACode.Next);
            Push(SubCode, AStr);
          end;
        end;
      end;
      case NFACode.Kind of
        nkNormal, nkChar:
          begin
            if NFACode.Code.IsEqual(AStr, Len) then
            begin
              NFACode := FStateList[NFACode.TransitTo];
              Inc(AStr, Len);
            end
            else
              NFACode := nil;
          end;
        nkEmpty:
          begin
            NFACode := FStateList[NFACode.TransitTo];
          end;
        nkEnd:
          begin
            FRegExp.FMatchData.EndP[0] := AStr;
            Result := True;
            Exit;
          end;
        nkMatchEnd, nkNoBackTrackEnd:
          begin
            NFACode := FStateList[NFACode.TransitTo];
            Result := True;
            Exit;
          end;
        nkGroupStart:
          begin
            FRegExp.FMatchData.StartP[NFACode.GroupIndex] := AStr;
            NFACode := FStateList[NFACode.TransitTo];
          end;
        nkGroupEnd:
          begin
            FRegExp.FMatchData.EndP[NFACode.GroupIndex] := AStr;
            NFACode := FStateList[NFACode.TransitTo];
          end;
        nkNoBackTrackBegin:
          begin
            NFACode := FStateList[NFACode.TransitTo];
            if not MatchCore(NFACode, AStr) then
            begin
              Result := False;
              Exit;
            end;
          end;
        nkAheadMatch:
          begin
            SubP := AStr;
            NFACode := FStateList[NFACode.TransitTo];
            if not MatchCore(NFACode, SubP) then
            begin
              Result := False;
              Exit;
            end;
          end;
        nkAheadNoMatch:
          begin
            SubP := AStr;
            NFACode := FStateList[NFACode.TransitTo];
            if MatchCore(NFACode, SubP) then
            begin
              Result := False;
              Exit;
            end;
          end;
      end;
      if NFACode = nil then
      begin
        SubP := AStr;
        Pop(NFACode, AStr);
        if SubP > AStr then
          FRegExp.FMatchData.Back(SubP - AStr);
      end;
    end;
  finally
    DestroyStack;
  end;
end;

アトミックグループ、先読み、後読みを再帰で処理するようにした。

再帰を使わなくてもできるのだが、深い再帰は起こらないし、この方がわかりやすいので。

コメントを残す

メールアドレスが公開されることはありません。