ソースコードのスターウォーズ

私は長い間、quainsに関連する興味深い何かを実装するという考えを持っていました。 そして最後に、この問題を終わらせることが判明しました。 ライフゲームの実装をソースコードで見たとき： Life of Self Printing Gameと似たようなことをしたかった。 熟考した後、 ASCIIグラフィックがあることを思い出しました。 しかし、ASCIIグラフィックスでアニメーションを作成することはさらに面白く、困難になります。 長い間サンプルを探す必要はありませんでしたが、ほとんどすぐにスターウォーズのアニメーション、またはAsciimationと呼ばれる4つの新しい希望のエピソードを見つけました 。 日本のプログラマーである遠藤裕介の仕事「岸壁リレー」も、このアイデアを実装するように駆り立てました。 そのような「フィルム」を実装する過程で、私は他の多くの問題を解決しなければなりませんでしたが、後悔する必要はありませんでした。



結果のソースはgistです。 「表示」を容易にするために、アニメーション全体をひねるスクリプトも含まれています。 生成、インターフェース、およびその他のユーティリティのプロジェクト全体のソースコードは、githubにレイアウトされています： Freaky-Sources （私が既に書いた Quine palindromesはそこに含まれています）。 そのようなことは実際的な利点を持たないことは明らかであり、ただの楽しみのためだけです。

はじめに

クインのアニメーションは1つの方法でのみ表示できます。コンパイルごとに次の各フレームをコンソールに出力します。 したがって、この場合の「ムービー」の速度は、コードのサイズ（コードが大きいほど、コンソールをコンパイルしてスクロールする時間が長くなる）、アンパックアルゴリズム、およびコンパイル速度（ハードウェア）に依存します。 さらに、コードは主に圧縮されたアニメーションフレームによって占有されます。



前述の「Game of Life」は、プログラムのソースコードの最初に初期化および表示されるフィールド文字列として使用します。 コードの量が少ない場合、このアプローチは受け入れられ、コンパイル中は常に表示されます。 ただし、私の場合、コードサイズは数百キロバイトです。つまり、フレームを最後に表示して表示できるようにする必要があります。 フレームを実際の行の形式ではなく、単一行のコメント（複数行も使用可能）の形式で出力することが決定されました。



IQが低いため、特別な能力がなく、頭の中で多数のパラメーターを操作することはできないため、クインを最大限に書き込むプロセスを自動化することにしました。 さらに、これにより、クインの構造をよりよく理解し、関連分野（NRefactoryを使用してC＃ソースコードを解析および処理）での経験を積むことができました。

クイン生成段階

したがって、私はクインを書くプロセスを次のステップに分割することにしました：

• コード生成。
• データ生成。
• コードの縮小。
• コードのフォーマット。
• キネ世代。

これらのすべての手順は、特別に設計されたテンプレートに対して実行されます。 スターウォーズに適用される「コード」とは、圧縮されたデータを解凍するコードを意味します。 そして、データはアニメーションフレームのパックされた配列です。 コードのテキストサイズを小さくするには、コードを読み取り不可にするために縮小が必要です。



確かに、最初は、圧縮データを解凍するための通常の.NETクラスGZip​​Streamでバージョンが記述されていました。 しかし、このクラスはこのプラットフォーム専用であることに加えて、スポーツではないと考えました。 したがって、私は自分のアーカイバでより複雑なバージョンを書きました。



これらの段階でナビゲートしやすくするために、WinFormsでインターフェイスを作成しました。

• 左上には、すべてのマーカーを備えたクインテンプレートが入力されるテキストボックスがあります。 それらの目的を以下に説明します。 このフィールドでは、最初の4つのステージが実行されます。
• 左下には、上記の手順を実行するためのさまざまなパラメーターとボタンがあります。 また、コンパイルを使用して、テンプレートのコードまたは結果のクインのエラーをすぐにチェックできます。
• 右上の最後の手順で生成されたクインコードで満たされたフィールド。
• コンパイル後のクインの次の反復が出力されるフィールドの右上。 また、クインをコンパイルし、フレームごとのアニメーション（または他の何か）を表示するプロセスをループするには、反復回数を含む[コンソール出力->出力]ボタンが必要です。

C＃構文を強調するために、 BigObfuscator FastColoredTextBoxコンポーネントが 使用されました 。 残念ながら、動作はかなり遅いため、結果の「映画」を通常のコンソールで見る方が便利です（残念ながら、あまり高速でもありません）。

クインパターン

テンプレートは、このような複雑なクインの出発点であり、次のようになります。



ご覧のとおり、上記のコードには多くのあいまいなコメントがあります。 しかし実際には、特定のコードまたはデータを挿入する場所を示すマーカーです。 このアプローチの利点は、クラスの他の完全なバージョンからコードを挿入でき、それらを順番にテストできることです（私はNUnitを使用しています）。 これらのマーカーを次のように分類しました。

• /*#...*/.../*...#*/-コード。 これらのマーカー間のコードの断片は、指定されたディレクトリのファイルによって検索されます。
• /*%...*/.../*...%*/-データ。 これらのマーカーの間に、特定のメソッドを使用して生成されたデータが挿入されます。これは、文字列形式（つまり、通常の文字列、文字列の配列、バイトの配列、整数など）で提示する必要があります。 一般的に、メソッドに関する情報をデータマーカーから抽出し、コンパイル済みのアセンブリで検索し、リフレクションを使用して呼び出すことができます。 しかし今のところ、必要なメソッドを手動で呼び出すことに限定することにしました。これはより普遍的なアプローチだからです（この方法で他の言語に移植する方が簡単です）。
• /*$...*/.../*...$*/-パラメーター。 これらのマーカーは、クインの表示の後続の反復ごとに変化するコードを示します。 それらは特別な表に示されており、置換のコードが示されています。 この場合、パラメーターは、現在のフレームの番号（毎回インクリメントされる）と、単一行のコメントを使用して実装される下のフレームの出力フィールドです。 いくつかのパラメーターはイントロンです。 次の反復でコードに影響を与えない行。 この場合、イントロンは出力フィールドです。
• / * @ * /-印刷。 これは特別なマーカーで、コード全体がクイン全体を表示するために実際に挿入されます。 単一のコピーにのみ存在します。 前の手順でコードとデータを生成した後、最後に置換が行われます。 データセクションの重複を防ぐため（クイーン自体とこの行に印刷しないように）、この段階で、データはデータ自体ではなくパラメーター（つまり、出力に含まれる「asdf」の代わり）に置き換えられることに注意してください'' '+出力+' "'は出力です）。

したがって、ステージとマーカーに関する情報を組み合わせて、次の図を作成できます。



ミニマライザーがクイン自体のパラメーターを変更しないままにしておくと、パラメーターに別の名前が付けられる状況が発生し、このため、クインがコンパイルされないか、必要でないものが出力されることに注意してください。 （確かに、パラメーターはまだ縮小されていますが、よりトリッキーな方法です）。



すべてのステージの詳細については、以下で説明します。

コード生成

コードを生成するとき、指定されたフォルダーのすべてのソースコードファイルが分析されます。 また、マーカー/*#...*/.../*...#*/の間のコードは、元のテンプレートの適切な場所にコピーされます。 たとえば、次の例では、HuffmanRle2クラス全体が/ *＃HuffmanRleDecode2 * // * HuffmanRleDecode2＃* /の間のセクションにコピーされます。 これらのマーカー内のコードの一部のフラグメントを無視するために（たとえば、.ToString（）メソッドはクインでは不要であり、デバッグに必要です）、このフラグメントを2つに分割せず、マーカー/ *＃Ignore * // * Ignore＃が導入されました* / 、これらのコード内のすべてのコードを無視できます。





さまざまなファイルから収集されたコードは、最小長の基準の観点から最適ではない可能性があるという事実にもかかわらず、 それにもかかわらず、それは標準スタイルで記述されていたため、このアプローチにより、生成の直前にクインデータを圧縮および抽出するためのテスト（NUnit）を記述および実行できました。これにより、開発プロセスが簡素化され、面倒が少なくなりました。 後で説明するコードの最小化により、このアプローチの欠点を実際に軽減できます。

データ生成

RLEやHuffmanコーディングなど、最も単純なロスレス圧縮アルゴリズムを使用してデータを圧縮しました。 ただし、このアニメーションは、他のフィルムと同様に、メインフレームと中間フレームに分割できます。 中間フレームには、最後のフレーム以降に変更された情報が含まれ、メインフレームにはフレームに関するすべての情報が含まれます。 したがって、中間フレームのすべての文字を取得するには、前のフレームをすべてメインフレームにデコードし、その後、受信した変更を考慮してすべてのフレームを現在のフレームにレンダリングする必要があります。 それは一種の擬似MPEGでした。 メインおよび中間フレームの構造を以下に示します。 通常のフレームと中間フレームに加えて、左、右、上下にシフトして得られる中間フレームを含めることを決定しました。



フレーム：

0..3-タイプ：

• 000-ベース：
  
  3..13-文字数
  
  13 ...-ハフマンRLEコード
• 001-左：
  
  010-トップ：
  
  011-右：
  
  100-下：
  
  101-変更：
  
  3..10-カウントの変更
  
  10 ...-変更

変更：

0..2-タイプ：

• 00-1文字：
  
  2..12-位置
  
  12 ...-ハフマンコード
• 01-水平線：
  
  2..12-位置
  
  12.19-文字数
  
  19 ...-ハフマンコード
• 10-垂直線：
  
  2..12-位置
  
  12..16-文字数
  
  16 ...-ハフマンコード

残念ながら、最終的な圧縮は希望するほど大きくはありませんでしたが、かなり許容範囲でした。 私は7-zipのlzmaレベルで、つまり 100 kb未満。 おそらく、より高度なメソッド（間隔コーディング、辞書メソッド）を使用すると、さらに高度な圧縮を実現できます。

コードの縮小

テキスト形式のコードのサイズを小さくするには、縮小が必要です。 C＃コードを処理するために、 NRefactoryライブラリが使用されました 。 Roslynに対する利点は、最小化タスクで必要なプロセスで解析ツリーを変更できることです。

クラス名、メソッド、フィールド、ローカル変数を短縮する

ミニファイヤの主なタスクは、まさにこの段階でした。 構築された構文ツリーをバイパスするために、Visitorパターンが使用されました。これは、深さを横断するときにノードを横断するために必要なメソッドのオーバーロードの形式で実装されました。



識別子の最小数を使用する一方で、重複しないようにしてコンパイルエラーを引き起こすために、短縮アルゴリズムは次の手順に分割されました。

• ローカル変数の縮小。 この段階で、 ローカル変数のすべての名前のリスト、定義からのメソッドの引数、およびツリー内の対応するノードが集約されます。 各変数は特定のメソッドに関連付けられています。 その後、1つのメソッド内の古い識別子ごとに、新しい識別子に置き換えられます。
• メンバータイプの縮小。 この段階で、ツリー内のすべてのフィールド名、 メソッド 、 プロパティ 、 列挙メンバー 、 イベント、およびそれらに対応するノードのリストが集約されます。 各メンバーは特定のタイプ（ class 、 structure 、 interface ）に関連付けられています 。 その後、1つのタイプ内の古い識別子ごとに、新しい識別子に置き換えられます。
• 型名の縮小。 この段階で、すべての型名（ クラス 、 構造体 、 インターフェース ）とそれに対応するツリー内のノードのリストが集約されます。 その後、各名前は新しい名前に置き換えられます。

置換を生成するには、最小の長さまたはランダムな識別子を生成できるクラスが使用されます。 このプロジェクトは最初のオプションを使用します。 各段階で置換を生成する場合、検出された識別子名は無視されます（そのため、交差点や潜在的なエラーはありません）。



ライブラリが無視された識別子をサポートしていることは注目に値します。 このプロジェクトで使用されている、何らかの理由で短縮すべきでないもの（クインパラメーター）。



使用される識別子へのすべてのリンクのリストを取得するには（Visual Studioですべての参照を検索）、NRefactory解決メカニズムが使用されます。 これを行うには、最初にツリーをコンパイルする必要があります（各段階：ローカル変数、型メンバー、型）：

 var unresolvedFile = SyntaxTree.ToTypeSystem(); var projectContent = projectContent.AddOrUpdateFiles(_unresolvedFile); var compilation = projectContent.CreateCompilation(); var resolver = new CSharpAstResolver(_compilation, SyntaxTree, _unresolvedFile);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、次のようにリンクを検索できます。

 var resolveResult = resolver.Resolve(node); var findReferences = new FindReferences(); ... findReferences.FindLocalReferences(); ... findReferences.FindReferencesInFile();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その他の縮小

次の小さな縮小も実装されました。

• プライベートキーワードの削除
• 名前空間の削除
• 変数初期化式の略語：
  
  

  •  List<byte> a = new List<byte>() -> var a = new List<byte>()
          
          
    
            
            
            
          
    
        
            
            
            
          
          
    
            
            
            
          
    
        
         

  •  var a = new b() -> ba = new b()
          
          
    
            
            
            
          
    
        
            
            
            
          
          
    
            
            
            
          
    
        
         

  
  
  注：この置換は、記事で説明されているテンプレート検索を使用して実行することもできます。
  
  NRefactoryを使用してCsharpコードを分析する
  
  
• 式が1つしかない中括弧を削除するif (a) { b; } => if (a) b;
  
  
  
  ： if (a) { b; } => if (a) b;



if (a) { b; } => if (a) b;
  
  
  
  
• ブール型を使用した比較レコードの削減： if (a == true) => if (a); if (a == false) => if (!a)



if (a == true) => if (a); if (a == false) => if (!a)
  
  
  
  
• リージョンとコメントの削除。

空白と改行の削除

あらゆる種類の縮小が行われた後、不要な空白と翻訳のみをコードから削除し、行の長さが特定の値を超えないようにします（美しさのため）。



ミニファイヤは別のプロジェクトで実装されており、 CSharp-Minifierからダウンロードできます。 これは、主にクインのコードを減らすことを目的として開発されたため、少し奇妙な機能を備えているという事実には驚くべきことはありません。 しかし、私はあなたのコメントおよび/またはプルクエストを喜んで受け入れます。

コードのフォーマット

この段階で、縮小されたコードをある種の画像のように見せることができます。 生成されたコードは基本的に単一の文字の配列であるため（破損する可能性があるため）、画像の作成が容易になるため、フォーマットは縮小後に正確に行われます。 シンボルが白いピクセルを表し、黒-その不在を表すように、画像は白黒形式のみにする必要があります。 より一致させるには、任意のヒューリスティックソートアルゴリズム（遺伝的）を使用できます。 私のフォーマットは実装されていません。

クインジェネレーション

次は、最終的な行を印刷するマーカーとして使用されました。/ * @ * /

段階的に、すべては次のようになります。 すべてのコードは完全に任意ですが、例では読みやすくするために改行が追加されています。

1. テンプレートの初期化：
   
   テンプレート=
   
   

    class P { static void Main() { var a = 6; /*@*/ int b = 10; } }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   
2. クインの印刷に使用する文字列テンプレートを生成します。 引用符、バックスラッシュ、および改行は、フォーマットされた文字列を表示するときに個別のパラメーターで表されるようにエスケープする必要があります。
   
   kernel = "var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});"
   
   
   
   
   
   
3. テンプレート内のマーカーを、前の手順の印刷に使用した行に置き換えます。 なぜなら C＃では、パラメーターの出力時に中括弧が使用されますが、エスケープする必要もあります。 これは、それらを複製することによって行われます。
   
   str = template.Replace("{", "{{").Replace("}", "}}").Replace("/*@*/", kernel)
   
   
   
   
   
   str =
   
   

    class P {{ static void Main() {{ var a = 6; var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1}); int b = 10; }} }}
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   
4. クインの印刷に使用される結果文字列の生成：
   
   insertToResult = "var s=\"" + str + "\""
   
   
   
   
   
   insertToResult =
   
   

    var s=" class P {{ static void Main() {{ int a=6; var s={1}{0}{1}; Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1}); int b=10; }} }}"; Console.Write(s,s,'"', '\\', "\r\n");
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   
5. ソーステンプレートのマーカーを結果の文字列に置き換えます。
   
   result = template.Replace("/*@*/", insertToResult)
   
   
   
   
   
   結果=
   
   

    using System; class c { static void Main() { int a=6; var s="using System;class c{{static void Main(){{int a=6;var s={1}{0}{1};Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});int b=10;}}}}"; Console.Write(s,s,'"', '\\', "\r\n"); int b=10; } }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

完了：自分自身を印刷できるプログラムが受信されました。

説明したアプローチは、パリンドロームキーの生成に一般化できますが、まだ実装していません。

打ち上げ

生成されたクインは、たとえばAsciimation.csファイルに保存され、次のコマンドで1つのフレームを出力できます。

"C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation







生成された「映画」全体を見るには、次のスクリプトを使用する必要があります。

 echo off SET /ai=0 :LOOP IF %i%==3591 GOTO END "C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation SET /ai=%i%+1 GOTO LOOP :END pause
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

この記事で説明されている原則は、他のプログラミング言語でのさまざまなクインの実装に適用できます。 残念ながら、オンラインサービス（ ideone.com 、 compileonline ）を使用すると、圧縮されているにもかかわらず最大サイズを超えているため、開発されたコードをテストすることはできません。



生成されたファイルとバッチファイルは、 AscimationQuine_1_3.7zからダウンロードできます。 将来的には、手動でだけでなく自動生成を使用して、チェーンウェインを実行し、おそらく遠藤裕介の偉業を繰り返すことができます。



特に、コンパイルする能力はないが、プロセスを確認したい場合：