Language.C の意味解析 (1)

気をとりなおして。 Haskell用の C言語のパーザライブラリ Language.C の意味解析機能を使ってみる。

まずはグローバルスコープのシンボルテーブルを表示してみる。

こんなことができる

入力 (sample.c)
enum enum1 {x, y, z};

void fundec1();

struct st1 {
  int a, b;
};

typedef struct st2_ {
  int c, d;
} st2;

static int i;
static int j = 2;
int k, l;
int m = 3;

static void staticfunc(){
}

int main(int argc, char** argv) {
  func();
  exit(-1);
}
実行
./test1 sample.c

(本来なら gcc -E とかで プリプロセスしたファイルを食わせないといけない。 sample.c はそれ自身で閉じているためそのまま食わせた。gcc -Eの処理もLanguage.Cに任せたい場合はProcessMain.hsのコメント参照)

出力
Global Declarations
    enumerators
            x  ~>  <econst enum1> x  =  0
            y  ~>  <econst enum1> y  =  1
            z  ~>  <econst enum1> z  =  2
    declarations
            fundec1  ~>  declaration fundec1 | function/external | void ()
    objects i  ~>  object i | static/internal | int
            j  ~>  object j | static/internal | int = 2
            k  ~>  object k | static/external | int
            l  ~>  object l | static/external | int
            m  ~>  object m | static/external | int = 3
    functions
            main  ~>  function main | function/external | int (int argc,
                                                               char * * argv)
            staticfunc  ~>  function staticfunc | function/internal | void ()
    tags    st1  ~>  struct st1 {a :: int; b :: int;}
            st2_  ~>  struct st2_ {c :: int; d :: int;}
            enum1  ~>  enum enum1 {x  =  0; y  =  1; z  =  2;}
    typeDefs
            st2  ~>  typedef st2 as struct st2_
            __builtin_va_list  ~>  typedef __builtin_va_list as va_list

うまくできてますね。
関数内の解析はまだできない模様。

ソースおよびコンパイル

ProcessMain.hs
module ProcessMain where

import System
import Language.C
import Language.C.System.GCC
import Control.Monad


-- Language.C を使ってソースを parse
parseMyFile :: FilePath -> IO CTranslUnit
parseMyFile input_file =
  do 
     content <- readFile input_file
     let parse_result = parseC (inputStreamFromString content) (Position input_file 0 0) -- プリプロセスしない場合
     -- parse_result <- parseCFile (newGCC "/usr/bin/gcc") Nothing [] input_file -- プリプロセスする場合
     case parse_result of
       Left parse_err -> error (show parse_err)
       Right ast      -> return ast

-- 第一引数のファイルを読み込み 処理
processMain :: (CTranslUnit -> IO ()) -> IO ()
processMain process = do
  [path] <- getArgs 
  ast <- parseMyFile path
  process ast
test1.hs
import System
import Language.C
import Language.C.Analysis
import ProcessMain
import Text.PrettyPrint

process unit = do
    putStrLn (fst $ either (error . show) id $ runTrav () trav)
  where
   trav = do
     decls <- analyseAST unit
     return (render $ pretty decls)

main = processMain process
コンパイル
ghc --make test1.hs

Language.C (cont.) - flexible array member(C99) を サイズ0の配列(GNU C互換)に変換

深追い日記．
jhcが生成した手元のコードを gcc 2.95でコンパイルするにはもうひとつ障害があった．

JHCはサンクを以下の構造体で管理するようだ：

typedef struct node {
        fptr_t head;
        sptr_t rest[];
} A_MAYALIAS node_t;

typedef struct dnode {
        what_t what;
        sptr_t rest[];
} A_MAYALIAS dnode_t;

ここで、 rest[] は flexible array member とよばれ、そのままだと(おおむね)サイズ0の配列として扱われる．この構造体を使うには、malloc(sizeof(node_t)+ほげほげ)のようにして、rest分の領域を確保する．

これのp.103, 6.7.2.1節の16に載ってます：
http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf

しかし gcc 2.95 は flexible array memberをサポートしてない．代わりに、GNU Cでサポートされている長さ0の配列を使うように変換したい．

5.12 Arrays of Length Zero - Using the GNU Compiler Collection (GCC)

flexible array memberを使っているのは現状ここだけなので、もうsedで書き換えても良い(もしくはjhcのコードを書き換えるか…)くらいなのだけど、あえて Language.Cでこれを実装した．

リファレンスとLanguage.C.Syntax.ASTの型名とにらめっこすれば大抵のことは分かるので気合いで書けます

converting flexible array member to an array of size 0

可読性が超悪くてごめんなさい

convFlexibleArrayMember :: CTranslUnit -> CTranslUnit
convFlexibleArrayMember = everywhere (mkT conv)
  where 
   conv :: CStructUnion -> CStructUnion
   conv (CStruct CStructTag ident (Just members@(_:_)) attrs ninfo) = CStruct CStructTag ident (Just $ init members ++ [conv_ $ last members]) attrs ninfo
   conv x = x
   conv_ (CDecl specs vars@(_:_) ninfo) = CDecl specs (init vars ++ [conv__ $ last vars]) ninfo
   conv_ x = x
   conv__ (Just (CDeclr ident vars@(_:_) lit attrs ninfo), cinit, expr) = (Just $ CDeclr ident (init vars++[convArrDeclr $ last vars]) lit attrs ninfo,cinit,expr)
   conv__ x = x
   convArrDeclr :: CDerivedDeclr -> CDerivedDeclr
   convArrDeclr (CArrDeclr quals (CNoArrSize False) ninfo) =  (CArrDeclr quals (CArrSize False (CConst (CIntConst (fromRight (readCInteger DecRepr "0")) (OnlyPos (Position (posFile $ posOfNode ninfo) 0 0))))) ninfo)
   convArrDeclr x = x
   fromRight (Right i) = i
   fromRight _ = error "impossible"

usage

こんな感じで使ってます：

arm-linux-gcc -E hs.out_code.c |./MoveVarDecls |./ConvIncompleteArray >converted.c && arm-linux-gcc -mstructure-size-boundary=8 converted.c

-mstructure-size-boundary=4 は ARM専用のオプションでアラインメントを4の倍数にするために使ってます (現状、意図通りに動いているもよう)嘘でした。boundaryは8の倍数でないとダメです。
JHCはポインタの下位2ビットをガベコレ用フラグと遅延評価フラグに使ってるのでこれをやらないとまずいことになるっぽいですこれをやってもassert failureは起きます。なんでだろう。

Language.C を使ってみる with Data.Generics

Language.CはHaskell用の、C言語のソースコードを構文解析するライブラリ。
構文木はHaskellのデータとして操作可能で、これのおかげでC言語のコードを色々と操作できる。意味解析に役立ついくつかの補助関数も定義されているようだ(よく調べてない)。

やったこと、動機

  • JHC (Haskellのコンパイラ；ISO C互換のコードを吐く)は C99のコードを吐くようだ
  • ツールの制約でgcc 2.95(19991024)しか手元にない。 gcc 2.95はC89しか受け付けないようだ
  • jhc が吐くコードを gcc 2.95 でコンパイルできるよう自動変換したい

そこで Haskell用の Cパーザである Language.C を使って、JHCが吐くコードを gcc 2.95でコンパイルできるように変換する。未完。

  • C89では 変数宣言が ブロックの頭以外に来たらエラー。全ての変数宣言をブロックの頭に移動させるコードを書いた。
  • Data.Generics という 木構造のトラバースに超便利なライブラリを使った。scrap your boilerplate(SYB)と呼ばれるアレだ。このページのサンプルコードだけで十分に価値は理解できるとおもう


C言語のコードをアレしてコレしてイチャイチャできたらなあという要望はどの業界でもありそうなので、これを機に皆でHaskellとLanguage.Cを使い始めるとよいと思います。

Language.C のインストール

  • happyをインストール
  • alexをインストール
  • haddockをインストール(haddockにリファレンスを生成させたい場合)

この後

darcs get http://code.haskell.org/language-c
cd language-c
runhaskell Setup.hs configure 
runhaskell Setup.hs build
sudo runhaskell Setup.hs install
runhaskell Setup.hs haddock # リファレンスが欲しい場合

ソースdownload

moveVarDecls.hs

使い方

このように変数の宣言をブロックの頭にもってくる．これだけでは jhcの吐くコードは gcc 2.95 ではコンパイルできないようだがそれはまた

-bash-3.2$ cat test.c 

void f2() {
}

void f1() {
	
	{
		int y=0, z=y+1;
		f2();
		int x=1;
	}
	f2();
	int y=2;
	
	for(int i=0; i<100; i++) {
		}
}
	

-bash-3.2$ ./moveVarDecls test.c 
void f2()
{
}
void f1()
{
    int y;
    {
        int y, z;
        int x;
        y = 0;
        z = y + 1;
        f2();
        x = 1;
    }
    f2();
    y = 2;
    for (int i = 0; i < 100; i++)
    {
    }
}

ソース

module Main where

import System
import Data.Generics
import Language.C
import Language.C.System.GCC

-- 第一引数のファイルを読み込み標準出力に出力
main = do
  (filename:[]) <- getArgs
  parseMyFile filename >>= (printMyAST . moveVarDecls)

-- Language.C を使ってソースを parse
parseMyFile :: FilePath -> IO CTranslUnit
parseMyFile input_file =
  do parse_result <- parseCFile (newGCC "gcc") Nothing [] input_file -- プリプロセスに使うgcc (cpp?) のパスを設定しよう
     case parse_result of
       Left parse_err -> error (show parse_err)
       Right ast      -> return ast

-- 表示
printMyAST :: CTranslUnit -> IO ()
printMyAST ctu = (print . pretty) ctu

-- Data.Generics (scrap your boilerplate) を使った、構文木のトラバース
moveVarDecls :: CTranslUnit -> CTranslUnit
moveVarDecls = everywhere (mkT moveVarDecls_)

-- ブロックの内容を宣言と代入文に分ける．
moveVarDecls_ :: [CBlockItem] -> [CBlockItem]
moveVarDecls_ bs = concat decls++concat stmts -- 宣言の後にブロックが来る
  where
    (decls,stmts) = unzip (map splitVarDecls bs)

-- 1つの変数宣言を宣言と代入文に分割する
splitVarDecls :: CBlockItem -> ([CBlockItem],[CBlockItem])
splitVarDecls (CBlockDecl (CDecl sp assign ninfo)) = ([mkDecl sp assign ninfo], mkStmts assign ninfo)
splitVarDecls x = ([],[x])

-- 宣言文から代入文を除去する．
-- sp 型、記憶子、修飾子のリスト
-- assign 変数名および代入文
-- ninfo ノード情報
mkDecl :: [CDeclSpec] -> [(Maybe CDeclr, Maybe CInit, Maybe CExpr)] -> NodeInfo -> CBlockItem
mkDecl sp assign ninfo = CBlockDecl (CDecl sp (map mkAssign assign) ninfo)
  where
    -- declr 変数名と、constやポインタ等の修飾子 (int *x; における *xの部分)
    -- init 代入文の右辺
    -- expr 構造体のフィールド宣言におけるビット長(ここではNothing)
    mkAssign (a@(_, Nothing, _)) = a 
    mkAssign (declr, Just init, expr) = (declr, Nothing, expr) -- 代入文を除去

-- 宣言文から代入文を抜き出す．
-- assign 変数名および代入文
-- ninfo ノード情報
mkStmts :: [(Maybe CDeclr, Maybe CInit, Maybe CExpr)] -> NodeInfo -> [CBlockItem]
mkStmts assign ninfo = concatMap mkExpr assign
  where
    mkExpr (Just (CDeclr (Just name) _ _ _ v_ninfo), Just (CInitExpr expr i_ninfo), _) 
      = [CBlockStmt (CExpr (Just (CAssign CAssignOp (CVar name v_ninfo) expr i_ninfo)) ninfo)] -- 代入文を生成
    mkExpr _ = []