目的

正規表現でやらかすことがそこそこあるので、c#のRegexが解釈した正規表現を可視化したい。
⇒~~図示はできていないが、~~内部構造を出力できた。

アプローチ

マッチした部分を可視化しようと思ったが（※）、オートマトン的なものが表示できたほうがうれしい気がしたので、ILSpy.exeでRegexクラス周辺をあさってみた。
(※：結局やってみた)

private Regex(string pattern, RegexOptions options, TimeSpan matchTimeout, bool useCache)

に下記のようなコードがあったので、下記3行目のcodeが使えそうと判断した。

Regexのコードから抜粋

// 注意：要所だけ抜粋して、間のコードも消してます。
1 if (cachedCodeEntry == null) {
2     RegexTree regexTree = RegexParser.Parse(pattern, roptions);
3     code = RegexWriter.Write(regexTree);
4     regexTree = null;
5 }
6 if (UseOptionC() && factory == null) {
7     code = null;
8 }

で、このメンバ code は Regex の internal なフィールドなのですが、
リフレクションで強引にアクセスできます。（普通はやっちゃダメ）

codeのクラスRegexCodeを見てみると、


internal const int Goto = 38;
internal int[] _codes;
internal string[] _strings;

オペコードっぽい定義がある。
というわけでこれを表示してみます。

出力結果

正規表現 abc(de)f を分析にかけてみた。
※ [a-c]とかをかけると、stringsに表示できないデータが含まれるので注意。

>regexReflectionTest.exe abc(de)f
--codes--
n:17
0:Lazybranch(16)
2:Setmark
3:Multi(0)
5:Setmark
6:Multi(1)
8:Capturemark(1,-1)
11:One(102)
13:Capturemark(0,-1)
16:Stop
--strings--
n:2
0:abc
1:de

どうやら
Multi は部分文字列を示す。(直後の_code[i+1]が_stringsのindex)
One は文字を示す。(直後の_code[i+1]が文字コード)
SetmarkとCapturemarkはMatchのGroupsで取り出せる情報と関係していそう。
といった感じ。

環境

RegexCodeクラスのコードが変わると正常に動作しない懸念があります。
下記で特定できているのか分からんですが、環境を晒しておきます。


C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe
Microsoft (R) Visual C# Compiler version 4.8.3752.0
for C# 5

ソースコード

ソースコード

regexReflectionTest.cs


using System;
using System.Drawing;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;
using System.Windows.Forms;
using System.Reflection;

class Test
{
    enum RegexCodeOpCode {
        Onerep = 0,
        Notonerep = 1,
        Setrep = 2,
        Oneloop = 3,
        Notoneloop = 4,
        Setloop = 5,
        Onelazy = 6,
        Notonelazy = 7,
        Setlazy = 8,
        One = 9,
        Notone = 10,
        Set = 11,
        Multi = 12,
        Ref = 13,
        Bol = 14,
        Eol = 15,
        Boundary = 16,
        Nonboundary = 17,
        Beginning = 18,
        Start = 19,
        EndZ = 20,
        End = 21,
        Nothing = 22,
        Lazybranch = 23,
        Branchmark = 24,
        Lazybranchmark = 25,
        Nullcount = 26,
        Setcount = 27,
        Branchcount = 28,
        Lazybranchcount = 29,
        Nullmark = 30,
        Setmark = 31,
        Capturemark = 32,
        Getmark = 33,
        Setjump = 34,
        Backjump = 35,
        Forejump = 36,
        Testref = 37,
        Goto = 38,
        Prune = 39,
        Stop = 40,
        ECMABoundary = 41,
        NonECMABoundary = 42,
        Mask = 63,
        Rtl = 64,
        Back           = 128,  // bit to indicate that we're backtracking.
        Back2          = 256,  // bit to indicate that we're backtracking on a second branch.
        Ci             = 512,  
    }
   

    [STAThread]
    public static void Main(string[] args)
    {
        if(args.Length==0)return;

        Regex r=null;

        try{
            r = new Regex(args[0]);
        }
        catch(Exception e){
            Console.WriteLine(e);
            return;
        }

        Type typeR = r.GetType();
        FieldInfo fieldRC = typeR.GetField("code", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        
        dynamic rc = fieldRC.GetValue(r);
        
        Type typeRC = rc.GetType();
        FieldInfo fieldRcCodes  = typeRC.GetField("_codes", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        FieldInfo fieldRcString = typeRC.GetField("_strings", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);

        MethodInfo miOpcodeSize = typeRC.GetMethod("OpcodeSize", BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic);


        int[] t    = (int[])fieldRcCodes.GetValue(rc);
        string[] s = (string[])fieldRcString.GetValue(rc);
        
        Console.WriteLine("--codes--");

        Console.Write("n:");
        Console.WriteLine(t.Length);
        for(int i=0;i<t.Length;i++) {
            int x = t[i];
            Console.Write(i);
            Console.Write(":");
            Console.Write((RegexCodeOpCode)x);

            int argCount = ((int)miOpcodeSize.Invoke(null, new object[] {x} )) - 1;

            if (argCount > 0) {
                Console.Write("(");
                for(int j=i+1;j<=i+argCount&&j<t.Length;j++) {
                    if(j>i+1){Console.Write(",");}
                    Console.Write(t[j]);
                }
                Console.Write(")");
                i += argCount;
            }
            Console.WriteLine();
        }
        
        Console.WriteLine("--strings--");
        
        Console.Write("n:");
        Console.WriteLine(s.Length);
        for(int i=0;i<s.Length;i++) {
            Console.Write(i);
            Console.Write(":");
            Console.WriteLine(s[i]??"<<NULL>>");
        }
    }
}

参考サイト

分析追記

a|bb を分析してみた。


--codes--
n:15
0:Lazybranch(14)
2:Setmark
3:Lazybranch(9)
5:One(97)
7:Goto(11)
9:Multi(0)
11:Capturemark(0,-1)
14:Stop
--strings--
n:1
0:bb

↓の図解は手書き。

さらにその後

グラフ表示させてみた。※箱は手動でドラッグして配置


using System;
using System.Drawing;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;
using System.Windows.Forms;
using System.Reflection;


public class MyNode
{
    int _codeIndex; // RegexCode._codeのindex
    int _selfIndex; // nodeとしてのindex
    List<int> _destCodeIndices;
    int[] _destNodeIndices; // nodeとしてのindex
    string _textOpCode;
    string _text;
    bool _charClassNotFlag;

    public int CodeIndex{get{return _codeIndex;}}
    public int[] NextIndices{get{return _destNodeIndices;}} // 横着...

    public bool CharClassNotFlag{get{return _charClassNotFlag;}}

    public string Text{get{return _text;}}
    public string TextOpCode{get{return _textOpCode;}}

    public enum RegexCodeOpCode {
        Onerep = 0,//
        Notonerep = 1,
        Setrep = 2,//
        Oneloop = 3,//
        Notoneloop = 4,
        Setloop = 5,
        Onelazy = 6,//
        Notonelazy = 7,
        Setlazy = 8,//
        One = 9,//
        Notone = 10,//
        Set = 11,//
        Multi = 12,//
        Ref = 13,
        Bol = 14,
        Eol = 15,
        Boundary = 16,
        Nonboundary = 17,
        Beginning = 18,
        Start = 19,
        EndZ = 20,
        End = 21,
        Nothing = 22,
        Lazybranch = 23,//
        Branchmark = 24,//
        Lazybranchmark = 25,
        Nullcount = 26,
        Setcount = 27,
        Branchcount = 28,
        Lazybranchcount = 29,
        Nullmark = 30,//
        Setmark = 31,//
        Capturemark = 32,//
        Getmark = 33,
        Setjump = 34,
        Backjump = 35,
        Forejump = 36,
        Testref = 37,
        Goto = 38,//
        Prune = 39,
        Stop = 40,//
        ECMABoundary = 41,
        NonECMABoundary = 42,
        Mask = 63,
        Rtl = 64,
        Back           = 128,  // bit to indicate that we're backtracking.
        Back2          = 256,  // bit to indicate that we're backtracking on a second branch.
        Ci             = 512,  
    }

    
    public MyNode(int selfIndex, int codeIndex, RegexCodeOpCode opCode, int[] args, string[] strings)
    {
        _selfIndex = selfIndex;
        _codeIndex = codeIndex;
        _text = "";
        _textOpCode = "";
        
        switch ( opCode ) {
        case RegexCodeOpCode.Notone:/* through */
            _charClassNotFlag = true;
            break;
        default:
            _charClassNotFlag = false;
            break;
        }

        _destCodeIndices = new List<int>();

        switch ( opCode ) {
        case RegexCodeOpCode.Lazybranch:/* through */
        case RegexCodeOpCode.Branchmark:
            _destCodeIndices.Add(codeIndex + args.Length + 1);
            _destCodeIndices.Add(args[0]);
            break;
        case RegexCodeOpCode.Goto: 
            _destCodeIndices.Add(args[0]);
            break;
        case RegexCodeOpCode.Stop:
            break;
        default:
            _destCodeIndices.Add(codeIndex + args.Length + 1);
            break;
        }

        _textOpCode = opCode.ToString();
        
        switch ( opCode ) {
        case RegexCodeOpCode.Lazybranch:
            _textOpCode = "LazyBr";
            break;
        case RegexCodeOpCode.One:/* through */
        case RegexCodeOpCode.Notone:
            _text = MyParseCharClass(((char)args[0]).ToString());
            break;
        case RegexCodeOpCode.Onerep: // 指定回数繰り返し
            _textOpCode += "{"+args[1].ToString()+"}";
            _text = MyParseCharClass(((char)args[0]).ToString());
            break;
        case RegexCodeOpCode.Setrep: // 指定回数繰り返し
            _textOpCode += "{"+args[1].ToString()+"}";
            _text = MyParseCharClass(strings[args[0]]);
            break;
        case RegexCodeOpCode.Oneloop: // 0～最大で指定回数繰り返し
            _textOpCode += "{0 to "+args[1].ToString()+"}";
            _text = MyParseCharClass(((char)args[0]).ToString());
            break;
        case RegexCodeOpCode.Onelazy: // 0～最大で指定回数繰り返し (最短マッチ)
            _text = MyParseCharClass(((char)args[0]).ToString());
            break;
        case RegexCodeOpCode.Setlazy: // 0～最大で指定回数繰り返し (最短マッチ)
            _text = MyParseCharClass(strings[args[0]]);
            break;
        case RegexCodeOpCode.Set:
            _text = MyParseCharClass(strings[args[0]]);
            break;
        case RegexCodeOpCode.Multi:
            _text = MyParseCharClass(strings[args[0]]);
            break;
        default:
            break;
        }
    }

    public void UpdateDestIndices(List<MyNode> nodes)
    {
        _destNodeIndices = new int[_destCodeIndices.Count];
        for ( int i = 0 ; i < _destCodeIndices.Count ; i++ ) {
            _destNodeIndices[i] = -1;
            foreach ( MyNode node in nodes ) {
                if ( node._codeIndex == _destCodeIndices[i] ) {
                    _destNodeIndices[i] = node._selfIndex;
                    break;
                }
            }
            if ( _destNodeIndices[i] == -1 ) {
                throw new Exception("bug!!!");
            }
        }
    }

    public static string MyParseCharClass(string s)
    {
        StringBuilder sb = new StringBuilder();

        foreach ( char c in s ) {
            if ( (int)c<0x20 || ((int)c>=0x7F && (int)c<=0xFF) ) {
                sb.Append("[x" + ((int)c).ToString("X02")+"]");
            }
            else {
                sb.Append(c);
            }
        }
        return sb.ToString();
    }


    public static List<MyNode> CreateNodes(Regex r)
    {
        var nodes = new List<MyNode>();

        Type typeR = r.GetType();
        FieldInfo fieldRC = typeR.GetField("code", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        
        dynamic rc = fieldRC.GetValue(r);
        
        Type typeRC = rc.GetType();
        FieldInfo fieldRcCodes  = typeRC.GetField("_codes", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        FieldInfo fieldRcString = typeRC.GetField("_strings", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);

        MethodInfo miOpcodeSize = typeRC.GetMethod("OpcodeSize", BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic);


        int[] opCodes = (int[])fieldRcCodes.GetValue(rc);
        string[] strings = (string[])fieldRcString.GetValue(rc);
        
        int nodeCount = 0;

        for ( int i=0 ; i<opCodes.Length ; i++ ) {
            int x = opCodes[i];
            int argCount = ((int)miOpcodeSize.Invoke(null, new object[] {x} )) - 1;
            if ( argCount < 0 ) {
                throw new Exception("Unexcepted opcode size.");
            }

            int[] args = new int[argCount];

            for ( int j = 0 ; j < argCount ; j++ ) {
                if ( i+j+1 >= opCodes.Length ) {
                    throw new Exception("Argument parse error.");
                }
                args[j] = opCodes[i+j+1];
            }
            
            nodes.Add(new MyNode(nodeCount, i, (RegexCodeOpCode)x, args, strings));

            nodeCount++;
            i += argCount;
        }

        foreach ( var node in nodes ) {
            node.UpdateDestIndices(nodes);
        }

        return nodes;
    }
}


// 描画用
public class MyEdge
{
    int _fromIndex;
    int _toIndex;
    Point[] _travelPoints; // 経由点の座標 (両端座標はダミー)

    public Point[] TravelPoints{get{return _travelPoints;}} // ちょっと横着..


    public MyEdge(int fromI, int toI)
    {
        _fromIndex = fromI;
        _toIndex = toI;
        _travelPoints = new Point[2];
    }

    public void UpdateTerminalPoints(MyGraph graph)
    {
        _travelPoints[0] = graph.CenterPointOf(_fromIndex);
        _travelPoints[_travelPoints.Length-1] = graph.CenterPointOf(_toIndex);
        Point tmp0 = graph.MyIntersect(_fromIndex, _travelPoints[1]);
        Point tmp1 = graph.MyIntersect(_toIndex  , _travelPoints[_travelPoints.Length-2]);
        _travelPoints[0]                      = tmp0;
        _travelPoints[_travelPoints.Length-1] = tmp1;
    }
}

public class MyGraph
{
    List<MyNode> _nodes;
    Rectangle[] _rects; // same length of _nodes

    List<MyEdge> _edges;

    public Point CenterPointOf(int i)
    {
        return new Point( ( _rects[i].Left + _rects[i].Right  ) / 2 ,
                          ( _rects[i].Top  + _rects[i].Bottom ) / 2 );
    }
    
    public MyGraph(List<MyNode> nodes)
    {
        _nodes = nodes;

        _rects = new Rectangle[nodes.Count];

        for ( int i = 0 ; i < _rects.Length ; i++ ) {
            _rects[i] = new Rectangle(new Point(5+i*60, 100), new Size(50,50));
        }
        if ( _rects.Length > 0 ) {
            _rects[0].Y -= 50;
        }
        if ( _rects.Length >= 2 ) {
            _rects[_rects.Length-1].Y -= 50;
        }

        _edges = new List<MyEdge>();

        for ( int i=0 ; i<nodes.Count ; i++ ) {
            foreach ( int toI in nodes[i].NextIndices ) {
                _edges.Add(new MyEdge(i,toI));
            }
        }
    }


    public void DrawGraph(Graphics g, Font fnt)
    {
        Pen pen = new Pen(Color.Blue, 1.5f);
        pen.CustomEndCap = new System.Drawing.Drawing2D.AdjustableArrowCap(4, 4); // 矢印

        foreach ( MyEdge edge in _edges ) {
            edge.UpdateTerminalPoints(this);
            g.DrawLines(pen, edge.TravelPoints);
        }

        for ( int i = 0 ; i < _rects.Length ; i++ ) {
            Rectangle rect = _rects[i];
            if ( rect.Width >= 1 ) {
                g.FillRectangle(Brushes.White, rect);
                g.DrawRectangle(Pens.Blue,     rect);
                g.DrawString(_nodes[i].CodeIndex.ToString(), fnt, Brushes.Blue,  rect.Left+2, rect.Top);
                g.DrawString(_nodes[i].TextOpCode,           fnt, Brushes.Blue,  rect.Left+2, rect.Top+18);
                g.DrawString(_nodes[i].Text,                 fnt, Brushes.Black, rect.Left+2, rect.Top+36);
            }
        }
    }

    public int MyHitTest(Point p, out Point location)
    {
        // 昇順で検索すると、z-order（描画の順序）が奥のほうを先に拾ってしまうので、降順で検索する
        for ( int i = _rects.Length - 1 ; i>=0 ; i-- ) {
            if ( _rects[i].Contains(p) ) {
                location = _rects[i].Location;
                return i;
            }
        }
        location = new Point(0,0);
        return -1;
    }

    public void MoveNodeTo(int nodeIndex, Point p)
    {
        _rects[nodeIndex].X = p.X;
        _rects[nodeIndex].Y = p.Y;
    }

    // a が -intmax の場合はダメだけど..
    private int MyAbsInt(int a)
    {
        return (a<0)?(-a):a;
    }

    // p <---> CenterPointOf(nodeIndex)(=cと置く) をつなぐ線L(端点をcとする半直線)と、rectの交点を求める
    public Point MyIntersect(int nodeIndex, Point p)
    {
        // まず、cを中央にもつ長方形rectと、半直線Lの交点がどの線と交わるかを判定する
        // (memo: y座標は数学の座標系で考える)
        //
        // ＼1 ／
        // 2 c 0
        // ／ 3＼
        //
        // 傾きと、x同士,y同士の大小関係から判定する。ゼロ除算に注意する。

        Point t = new Point();
        Point c = CenterPointOf(nodeIndex);
        int W = _rects[nodeIndex].Width;
        int H = _rects[nodeIndex].Height;

        if ( W == 0 || H == 0 ) { // 例外処理
            return c;
        }
        if ( p.X == c.X && p.Y == c.Y ) { // 例外処理
            return c;
        }

        //   abs((p.Y-c.Y)/(p.X-c.X)) <= H/W  なら  領域0か2
        if ( MyAbsInt(p.Y-c.Y)*(long)W <= MyAbsInt(p.X-c.X)*(long)H ) {
            int dY = (int)((((long)W/2) * (p.Y-c.Y))/(p.X-c.X));
            // p.X==c.X なら、p.Y==c.Yであり、先の例外処理でこのifには入らないのでゼロ除算は回避できる(W>0が前提)

            if ( c.X < p.X ) {
                t.X = c.X + W/2;
                t.Y = c.Y + dY;
            }
            else{
                t.X = c.X - W/2;
                t.Y = c.Y - dY;
            }
        }
        else {
            int dX = (int)((((long)H/2) * (p.X-c.X))/(p.Y-c.Y));

            if ( c.Y < p.Y ) {
                t.X = c.X + dX;
                t.Y = c.Y + H/2;
            }
            else{
                t.X = c.X - dX;
                t.Y = c.Y - H/2;
            }
        }

        return t;
    }
}



class Test : Form
{
    MyGraph graph;
    PictureBox pct;
    const int WIDTH = 800;
    const int HEIGHT = 300;
    Font fnt;
    Point dragStartPoint;
    Point dragInitialNodeLocation;
    int dragStartNodeIndex;

    Test(Regex r)
    {   
        fnt = this.Font;
        dragStartNodeIndex = -1;

        ClientSize = new Size(WIDTH, HEIGHT);

        pct = new PictureBox();
        pct.Dock = DockStyle.Fill;
        pct.Image = new Bitmap(WIDTH, HEIGHT);
        Controls.Add(pct);

        Console.WriteLine("Creating regex nodes...");
        List<MyNode> nodes = MyNode.CreateNodes(r);
        Console.WriteLine("done.");

        graph = new MyGraph(nodes);

        Load += (sender, e)=>{RedrawGraph();};
        pct.MouseDown += Pct_MouseDown;
        pct.MouseMove += Pct_MouseMove;
        pct.MouseUp   += (sender,e)=>{dragStartNodeIndex = -1;};
    }

    void RedrawGraph()
    {
        Graphics g = Graphics.FromImage(pct.Image);
        g.Clear(Color.LightGray);
        graph.DrawGraph(g, fnt);
        g.Dispose();
        pct.Refresh();
    }

    void Pct_MouseDown(object sender, MouseEventArgs e)
    {
        if ( (e.Button & MouseButtons.Left) == MouseButtons.Left ) {
            dragStartPoint = e.Location;
            dragStartNodeIndex = graph.MyHitTest(dragStartPoint, out dragInitialNodeLocation);
        }
    }

    void Pct_MouseMove(object sender, MouseEventArgs e)
    {
        if ( (e.Button & MouseButtons.Left) == MouseButtons.Left ) {
            if ( dragStartNodeIndex >= 0 ) {
                if ( e.X > 0 && e.Y > 0 && e.X < WIDTH && e.Y < HEIGHT ) {
                    Point p = new Point();
                    p.X = dragInitialNodeLocation.X + (e.X - dragStartPoint.X);
                    p.Y = dragInitialNodeLocation.Y + (e.Y - dragStartPoint.Y);
                    graph.MoveNodeTo(dragStartNodeIndex, p);
                    RedrawGraph();
                }
            }
        }
    }

    [STAThread]
    public static void Main(string[] args)
    {
        if(args.Length==0)return;

        Regex r=null;

        Console.WriteLine("Creating regex...");
        try{
            r = new Regex(args[0]);
            Console.WriteLine("done.");
        }
        catch(Exception e){
            Console.WriteLine(e);
            return;
        }

        Application.Run(new Test(r));
    }
}