Чиним f-spot

Я использую f-spot в качестве менеджера коллекций фотографий на своем домашнем компьютере. К сожалению, начиная с версии 0.8.0 f-spot испортился: тамбнейлы превратились в серые квадратики, а при клике на них фотографии открывались на долю секунды и f-spot тут же падал. Поиск в интернете вывел на баг #627745. В двух словах баг заключается в том, что если в пути к файлам с фотографиями встречаются директории с нелатинскими символами, то f-spot благополучно падает. В пути к моим фото присутствует директория Снимки/, так что мне не повезло.
Некоторое время я терпеливо ждал выхода следующей версии f-spot. Но, f-spot 0.8.2 вышел, а проблема осталась. Пришла пора действовать. Итак, для восстановления работоспособности f-spot была применена стратегия, состоящая из двух основных пунктов:

1. Сделать так, чтобы путь к файлам с фотографиями не содержал нелатинских символов
2. Сделать так, чтобы f-spot узнал об изменениях в пункте 1

Первый пункт достигается очень просто: нужно использовать старые добрые символические ссылки:

ln -s Снимки Pictures

Теперь к фотографиям можно обращаться через путь Pictures/ вместо Снимки/.
Чтобы реализовать второй пункт, нужно знать как f-spot хранит информацию о фотографиях. А делает он это с помощью базы данных photos.db, которая обычно находится в директории ~/.config/f-spot/. Редактировать эту БД можно с помощью утилиты sqlite3. Естественно, перед тем как изменять БД, неплохо создать ее резервную копию, просто скопировав файл photos.db. Итак, открываем БД для внесения нужных изменений:

sqlite3 photos.db

Эта команда загружает интерактивную среду sqlite. Для просмотра перечня таблиц вводим

sqlite> .tables
exports         meta            photo_versions  rolls         
jobs            photo_tags      photos          tags

Поля отдельной таблицы можно увидеть с помощью команды .schema:

sqlite> .schema photos
CREATE TABLE photos (
    id          INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL, 
    time            INTEGER NOT NULL, 
    base_uri        STRING NOT NULL, 
    filename        STRING NOT NULL, 
    description     TEXT NOT NULL, 
    roll_id         INTEGER NOT NULL, 
    default_version_id  INTEGER NOT NULL, 
    rating          INTEGER NULL 
);

Увидеть, где находятся данные, содержащие пути с директорией Снимки/ было просто: достаточно выполнить select * from для всех (или только подозрительных) таблиц. Оказалось, что данные о путях содержатся в полях base_uri таблиц photos и photo_versions.
Теперь нужно выполнить замену Снимки на Pictures во всех данных для этих полей:

sqlite> update photos set base_uri=replace(base_uri,"Снимки","Pictures")
   ...> where base_uri like "%Снимки%";
sqlite> update photo_versions set base_uri=replace(base_uri,"Снимки","Pictures")
   ...> where base_uri like "%Снимки%";

Всё. Выходим из среды sqlite:

sqlite> .quit

Теперь запускаем f-spot: тамбнейлы должны появиться, при клике на них фотографии должны показываться без проблем. Осталось изменить имя директории, в которую будут импортироваться фото в дальнейшем c Снимки на Pictures: это можно сделать прямо в f-spot из меню Правка -> Параметры.

P.S. Похоже, что этот баг не связан напрямую с f-spot, возможно он присутствует на уровне mono или Gnome.

P.P.S. Я пробовал использовать shotwell, но f-spot мне по-прежнему кажется симпатичней, несмотря на свою глючность. Возможно, в дальнейшем я перейду на shotwell, когда его допилят.

Вышел Geant4 9.4 и ChargeExchangeMC (aka Cexmc)

17 декабря вышла новая версия библиотеки для моделирования прохождения элементарных частиц в веществе Geant4 9.4. Geant4 широко применяется при моделировании физических экспериментов, а также в медицине и космофизике.
Для меня данный релиз замечателен тем, что в него в качестве одного из advanced examples вошла программа ChargeExchangeMC, автором которой я являюсь. Программа применялась для моделирования реального эксперимента в Петербургском Институте Ядерной Физики. Первая версия, написанная на фортране, была в дальнейшем переписана с нуля на C++ с использованием Geant4.
Основные особенности программы:

1. Это достаточно большой проект, он включает 71 заголовочный файл и 63 файла исходников, общий размер программного кода превышает 20 тысяч строк
2. Геометрия установки полностью описана в формате GDML. Это позволит гибко изменять описание установки без изменения исходного кода
3. Для упрощения анализа данных используются гистограммы на основе библиотеки CERN ROOT
4. Реализована модель реконструкции данных с гибкой настройкой различных параметров
5. В программе реализован гибкий алгоритм на основе шаблонов C++ для возможности легкого изменения изучаемых взаимодействий
6. Персистентное хранение данных реализовано с помощью библиотеки boost::serialization
7. Пользовательский фильтр данных позволяет изменять полученные данные с помощью специальных скриптов. Грамматика скриптов описана с помощью библиотеки boost::spirit
8. Run manager имеет уникальный режим проигрывания событий (replay mode), который позволяет пересчитывать уже имеющиеся данные с параметрами, отличными от исходных

Документацию по установке и использованию программы можно найти здесь.

Реорганизация структуры репозитория Subversion

Ситуация: Имеется репозиторий Subversion, который управляет среднего размера проектом, скажем my_project, уже в течение года. Соответственно, присутствует богатая история изменений. Но... Изначально структура репозитория была спланирована недальновидно, в частности были допущены следующие две оплошности:

1. Импорт исходного кода осуществлялся в корневую директорию, выделенную для Subversion
2. Не была создана промежуточная директория trunk/. Напомним, что в Subversion реализация хранения тегов и веток (в том числе главной) не различаются: фактически это просто разные поддиректории внутри проекта. Поэтому в Subversion обычно предлагается структурировать проект с использованием следующих канонических поддиректорий: trunk/ (для главной ветки), branches/ (для побочных веток) и tags/ (для тегов)

Первый пункт означает, что невозможно нормальным способом добавить еще один проект в корневую директорию Subversion (у меня она расположена в ~/svn/). Второй пункт означает, что невозможно нормальным способом создать теги и ветки для существующего проекта. Именно со второй проблемой я и столкнулся, когда всплыла необходимость выделить отдельную ветку для поддержания проекта при использовании старой версии одной из сторонних библиотек.

Постановка задачи: изменить существующий (или создать новый) репозиторий Subversion, в котором будет возможно создавать новые проекты, и в котором структура существующего проекта будет приведена к канонической (с использованием трех поддиректорий trunk/, branches/ и tags/), и при этом будет сохранена в работоспособном состоянии история всех изменений данного проекта без добавления служебных ревизий в ее начало.

Решение: будем создавать новый репозиторий. Для этого сначала выполним дамп существующего репозитория в файл:

svnadmin dump ~/svn/ > my_project_svn_dump

Теперь, предварительно забекапив директорию ~/svn/, удаляем все, что в ней находится, и создаем новый репозиторий для проекта my_project:

svnadmin create ~/svn/my_project

Теперь нам нужно загрузить дамп истории в новый репозиторий. Но предварительно его следует отредактировать (дамп репозитория представляет собой обычный ASCII файл), сохранив на всякий случай исходную копию. Поскольку в старый репозиторий проект был импортирован из директории my_project/, а имя нового репозитория уже содержит название my_project, то нам нужно удалить все упоминания об этой директории внутри файла. Однако, мы поступим проще: нам ведь все равно нужна поддиректория trunk/, так что зачем удалять упоминания о my_project/ внутри дампа, когда это можно просто заменить на trunk/? Итак, ищем строку

Node-path: my_project

и заменяем ее на

Node-path: trunk

Кроме того, my_project входит в состав путей к файлам, поэтому ищем все вхождения

Node-path: my_project/

и заменяем их на

Node-path: trunk/

Замену вхождений легко автоматизировать с помощью текстового редактора, например vim.
А теперь загружаем отредактированный дамп старого репозитория в новый:

svnadmin load ~/svn/my_project < my_project_svn_dump

Если все прошло успешно, то нас можно поздравить: новый репозиторий будет содержать всю историю изменений из старого репозитория без каких-либо дополнений.
Осталось добавить директории branches/ и tags/ (я перенесу части строки для удобства, на самом деле это однострочная команда):

svn mkdir -m "branches and tags directories added"
    file:///home/user/svn/my_project/tags
    file:///home/user/svn/my_project/branches

Теперь можно делать чекаут из нового репозитория и продолжать работу с проектом:

svn co file:///home/user/svn/my_poject/trunk my_project

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

Отключение автоматического монтирования отдельных разделов диска устройства, подключаемого через USB

Имеется в наличии медиаплеер Iconbit HDR12L, в который установлен внутренний диск размером 500Гб. Диск был размечен устройством следующим образом:

Устр-во Загр     Начало       Конец       Блоки     Id  Система
/dev/sdc1           16065   967386104   483685020    7  HPFS/NTFS
/dev/sdc2       967386105   967707404      160650   82  Linux своп / Solaris
/dev/sdc3       967707405   976125464     4209030   83  Linux
/dev/sdc4       976125465   976446764      160650   83  Linux 

При обмене файлов с компьютером интерес представляет только первый раздел с NTFS системой. Но по умолчанию в моем дистрибутиве (Fedora 14) монтируются все три раздела (исключение составляет 2-ой раздел с подкачкой). Соответственно, задача формулируется следующим образом: отключить автоматическое монтирование разделов /dev/sdc3 и /dev/sdc4 при подключении медиаплеера через USB.
За работу со съемными носителями в Linux традиционно отвечают две подсистемы: udev и hal. Первая подсистема привязывает устройства к корневой файловой системе в директории /dev, а вторая работает на более высоком уровне и определяет что делать с новым устройством: для съемных носителей это что обычно заключается в монтировании носителя в корневую файловую систему. Соответственно, нас интересует уровень hal и мы создаем новое правило hal для медиаплеера iconbit и помещаем его в новый файл /etc/hal/fdi/policy/90-iconbit.fdi. Вот его содержимое:

<?xml version="1.0" encoding="UTF-8"?>

<deviceinfo version="0.2">
  <device>
    <match key="volume.label" string_outof="iconbit_p3;iconbit_p4">
      <merge key="volume.ignore" type="bool">true</merge>
    </match>
  </device>
</deviceinfo>

На этом примере видно, что правила hal записываются в формате xml. В нашем правиле будут проверяться метки разделов: если метка раздела совпадает с iconbit_p3 или iconbit_p4, то он не будет монтироваться (значение volume.ignore для таких разделов устанавливается в true). Важно отметить, что удобные метки разделов я установил сам. Вместо проверки на совпадение метки раздела можно установить проверку на совпадение с uuid раздела: в этом случае ключом будет не volume.label, а volume.uuid. Атрибут string_outof соответствует выбору между несколькими вариантами, разделенными точкой с запятой; если нужно осуществлять проверку только для одного варианта, то вместо string_outof нужно использовать string.
Всё. Прекрасно. Перезапускаем hal и оно ... не работает. Проблема в том, что в новых дистрибутивах (в Fedora начиная с версии 11) для работы со съемными носителями вместо hal используется подсистема udisks из DeviceKit. В udisks несколько иной подход, и здесь нам таки придется добавлять правила на уровне udev. Итак, создаем файл /etc/udev/rules.d/90-iconbit.rules co следующим содержимым:

# iconbit auxiliary partitions
ENV{ID_FS_TYPE}=="ext3", \
  ENV{ID_FS_LABEL}=="iconbit_p3|iconbit_p4", \
  ENV{UDISKS_PRESENTATION_HIDE}="1"

Теперь, после перезагрузки компьютера, цель достигнута: при подключении медиаплеера к компьютеру через USB монтируется только один раздел с NTFS.
Примеры использования правил udisks можно найти в файле  /lib/udev/rules.d/80-udisks.rules.

Update. В Fedora 17, а может быть даже раньше, система udisks была заменена на udisks2, в которой синтаксис правил опять изменился. Теперь правило для iconbit выглядит так:

# iconbit auxiliary partitions
ENV{ID_FS_TYPE}=="ext3", \
  ENV{ID_FS_LABEL}=="iconbit_p3|iconbit_p4", \
  ENV{UDISKS_IGNORE}="1"

Кроме того, файлы правил теперь находятся в директории /usr/lib/udev/rules.d/. И еще, лично я переименовал 90-iconbit.rules в 98-iconbit.rule (хотя конкретное значение численного префикса в названии файла не играет существенной роли до тех пор, пока указанные в нем правила не пересекаются с правилами из других файлов в этой директории).

Реализация парсера пользовательского языка на Haskell

Итак, я выкладываю версию парсера пользовательского языка с поддержкой арифметических выражений с функциями и переменными, написанную на функциональном языке Haskell. С грамматикой языка можно ознакомиться, прочитав мое первое сообщение в этом блоге. Задачей программы, как и прежде, будет построение абстрактного синтаксического дерева (AST) для отдельных инструкций языка. В отличие от версии, написанной на boost::spirit, я не стал реализовывать базовый эвалюатор полученных деревьев, хотя сделать это не сложно.

В качестве лексера и грамматического анализатора я использовал alex и happy соответственно, которые входят в состав Haskell Platform; alex анализирует исходный код лексера (с расширением .x), а happy анализирует исходный код грамматики (с расширением .y). Обе программы генерируют соответствующие файлы с расширением .hs. Фактически, исходные коды лексера и грамматики состоят по большей части из кода на Haskell (все, что находится в этих файлах в фигурных скобках, является валидным кодом Haskell), и лишь небольшое количество мета-объявлений предназначено для предварительной обработки alex и happy.

Описание грамматики языка для happy совместимо с описанием для boost::spirit несмотря на то, что внутренне эти два генератора парсеров реализованы по-разному (happy генерирует LALR парсер, а spirit - парсер с рекурсивным спуском). Хотя проблема левой рекурсии в happy исчезает, и, кроме того, happy предоставляет дополнительные возможности вроде указания приоритета операторов, я не стал изменять реализацию грамматики по сравнению с версией для boost::spirit.

Итак, грамматика нашего пользовательского языка в версии haskell / happy выглядит следующим образом:

Statement : Action Condition { ParseResult $1 $2 }

Action : keep tpt    { KeepTpt }
       | keep edt    { KeepEdt }
       | delete tpt  { DeleteTpt }
       | delete edt  { DeleteEdt }

Condition :: { Subtree }
Condition : if Expression { buildTopTree $2 }

Expression :: { Node }
Expression : OrExpression { $1 }

PrimaryExpression : Function1 { buildFunction1Subtree $1 }
                  | '(' Expression ')' { setPriorityInOperatorTree 0 $2 }
                  | LeafOperand { Leaf $1 }

LeafOperand : Constant { Constant $1 }
            | Variable { Variable $1 }

Constant : double { DoubleValue $1 }
         | integer { IntegerValue $1 }

Variable : identifier '[' integer ',' integer ']' { Vector2 $1 $3 $5 }
         | identifier '[' integer ']' { Vector1 $1 $3 }
         | identifier { Scalar $1 }

Function1 : identifier '(' Expression ')' { Function1 $1 $3 }

OrExpression : AndExpression '|' OrExpression
               { buildOperatorSubtree ( Op ( LogOp Or ) 1 False ) $1 $3 }
             | AndExpression { $1 }

AndExpression : Relation '&' AndExpression
                { buildOperatorSubtree ( Op ( LogOp And ) 2 False ) $1 $3 }
              | Relation { $1 }

Relation : Addition RelOperator Addition
           { buildOperatorSubtree ( Op ( RelOp $2 ) 3 False ) $1 $3 }
         | Addition { $1 }

Addition : Multiplication AddOperator Addition
           { buildOperatorSubtree ( Op ( AddOp $2 ) 4 False ) $1 $3 }
         | Multiplication { $1 }

Multiplication : UnaryExpression MultOperator Multiplication
                 { buildOperatorSubtree ( Op ( MultOp $2 ) 5 False ) $1 $3 }
               | UnaryExpression { $1 }

UnaryExpression : UnaryOperator PrimaryExpression
                  { buildUnaryOperatorSubtree ( Op ( UnaryOp $1 ) 6 True ) $2 }
                | PrimaryExpression { $1 }

UnaryOperator : '-' { UMinus }
              | '!' { Not }

MultOperator : '*' { Mult }
             | '/' { Div }

AddOperator : '+' { Plus }
            | '-' { Minus }

RelOperator : "<=" { LessEqual }
            | ">=" { MoreEqual }
            | "!=" { NotEqual }
            | "<" { Less }
            | ">" { More }
            | "=" { Equal }

happy пользуется определениями токенов из лексера, импортируя его модуль CfLexer. Эти токены (keep, delete, tpt, edt, if, арифметические операторы) сопоставляются с типами лексера и перечислены в секции %token. В фигурных скобках описания грамматики указываются семантические действия, которые должны соответствовать построению объекта необходимого типа, как это сделано и в boost::spirit. Поскольку в Haskell реализован автоматический вывод типов на основе модели Хиндли-Милнера, то формально указывать типы выражений нет необходимости, хотя в двух случаях, для наглядности, я определил типы выражений Condition :: { Subtree } и Expression :: { Node }. Типы выражений определены ниже в этом же файле:

data  Statement =
    ParseResult
    {
        action    :: Action,
        condition :: Subtree
    }

data  Action =
    KeepTpt                  |
    KeepEdt                  |
    DeleteTpt                |
    DeleteEdt
    deriving Show

data  Node =
    Tree Subtree             |
    Leaf LeafOperand
    deriving Show

data  Subtree =
    Subtree
    {
        nodeType :: NodeType,
        children :: [ Node ]
    }
    deriving Show

data  NodeType =
    Operator  Operator       |
    Function  Function
    deriving Show

data  Operator =
    Op
    {
        op         :: OperatorType,
        priority   :: Int,
        hasRLAssoc :: Bool
    }

data  OperatorType =
    Uninitialized            |
    Top                      |
    UnaryOp  UnaryOperator   |
    MultOp   MultOperator    |
    AddOp    AddOperator     |
    RelOp    RelOperator     |
    LogOp    LogOperator

data UnaryOperator =
    UMinus                   |
    Not

data MultOperator =
    Mult                     |
    Div

data AddOperator =
    Plus |
    Minus

data RelOperator =
    LessEqual                |
    MoreEqual                |
    NotEqual                 |
    Less                     |
    More                     |
    Equal

data LogOperator =
    And |
    Or

data  Function =
    FunctionName  String

data  LeafOperand =
    Variable  Variable       |
    Constant  Constant
    deriving Show

data  Constant =
    DoubleValue   Double     |
    IntegerValue  Int

data  Variable =
    Scalar   String          |
    Vector1  String Int      |
    Vector2  String Int Int

data Function1 =
    Function1
    {
        fName :: String,
        fExpr :: Node
    }

Все типы являются алгебраическими в понятии Haskell, то есть создаются с использованием ключевого слова data и могут иметь один и более конструкторов. Некоторые из типов наследуют определения класса Show, что позволит выводить их на экран компьютера. Поскольку дефолтный вывод некоторых типов на экран меня не удовлетворил, я переопределил для них функцию show:

instance Show Operator where
    show = showOperator

showOperator ( Op a _ _ ) = 
    "-op- " ++ case a of
                    Uninitialized   -> "UNINITIALIZED"
                    Top             -> "Top"
                    UnaryOp UMinus  -> "u -"
                    UnaryOp Not     -> "!"
                    MultOp Mult     -> "*"
                    MultOp Div      -> "/"
                    AddOp Plus      -> "+"
                    AddOp Minus     -> "-"
                    RelOp LessEqual -> "<="
                    RelOp MoreEqual -> ">="
                    RelOp NotEqual  -> "!="
                    RelOp Less      -> "<"
                    RelOp More      -> ">"
                    RelOp Equal     -> "="
                    LogOp And       -> "&"
                    LogOp Or        -> "|"

instance Show Function where
    show = showFunction

showFunction ( FunctionName a ) = "-fun- " ++ a

instance Show Variable where
    show = showVariable

showVariable ( Scalar a ) = a
showVariable ( Vector1 a b ) = a ++ "[" ++ show b ++ "]"
showVariable ( Vector2 a b c ) = a ++ "[" ++ show b ++ "," ++ show c ++ "]"

instance Show Constant where
    show = showConstant

showConstant ( DoubleValue a ) = show a
showConstant ( IntegerValue a ) = show a

Окончательный вывод на экран дерева для отдельной инструкции будет осуществляться с помощью функции printResult и ее вспомогательными функциями:

printResult :: Statement -> IO ()
printResult x = do
    putStrLn $ "Result: action = " ++ show ( action x ) ++ ", parsed tree = "
    putStrLn ""
    printSubtree ( condition x ) ""

printSubtree :: Subtree -> String -> IO ()
printSubtree ( Subtree a b ) is = do
    putStrLn $ is ++ case a of
                        Operator aa -> show aa
                        Function aa -> show aa
    printChildren b $ is ++ "    "

printChildren :: [ Node ] -> String -> IO ()
printChildren [] _ = return ()

printChildren ( Tree x : xs ) is = do
    printSubtree x is
    printChildren xs is

printChildren ( Leaf x : xs ) is = do
    putStrLn $ is ++ printLeaf x
    printChildren xs is

printLeaf :: LeafOperand -> String
printLeaf a = case a of
                    Variable aa -> show aa
                    Constant aa -> show aa

При построении AST использовались вспомогательные функции:

buildTopTree :: Node -> Subtree
buildTopTree ( Tree x ) = x
buildTopTree x@( Leaf _ ) =
    Subtree ( Operator $ Op Top 0 False ) [ x ]

buildFunction1Subtree :: Function1 -> Node
buildFunction1Subtree x =
    Tree $ Subtree ( Function . FunctionName $ fName x ) [ fExpr x ]

buildOperatorSubtree :: Operator -> Node -> Node -> Node
buildOperatorSubtree a@( Op _ _ True ) nl nr =
    Tree $ Subtree ( Operator a ) [ nl, nr ]

buildOperatorSubtree a nl nr@( Tree sr@( Subtree ( Operator b ) ( cnrl : _ ) ) )
    | p == priority b =
        Tree $ moveDownLeft ( Subtree ( Operator a ) $
                                      nl : [ getDeepestLeft cnrl p ] ) sr
    | otherwise =
        Tree $ Subtree ( Operator a ) [ nl, nr ]
        where p = priority a

buildOperatorSubtree a nl nr =
    Tree $ Subtree ( Operator a ) [ nl, nr ]

getDeepestLeft :: Node -> Int -> Node
getDeepestLeft x@( Leaf _ ) _ = x

getDeepestLeft x@( Tree ( Subtree ( Operator b ) ( cnl : _ ) ) ) p
    | p == priority b = getDeepestLeft cnl p
    | otherwise = x

getDeepestLeft x _ = x

moveDownLeft :: Subtree -> Subtree -> Subtree
moveDownLeft sl ( Subtree b@( Operator _ ) ( ( Leaf _ ) : cnrr ) ) =
    Subtree b $ Tree sl : cnrr

moveDownLeft sl@( Subtree ( Operator _ ) _ )
             ( Subtree b@( Operator _ )
                       ( ( Tree ( Subtree ( Function _ ) _ ) ) : cnrr ) ) =
    Subtree b $ Tree sl : cnrr

moveDownLeft sl@( Subtree ( Operator a ) _ )
             ( Subtree b@( Operator _ )
                       ( ( Tree csrl@( Subtree ( Operator c ) _ ) ) : cnrr ) )
    | priority a == priority c =
        Subtree b $ Tree ( moveDownLeft sl csrl ) : cnrr
    | otherwise =
        Subtree b $ Tree sl : cnrr

moveDownLeft sl _ = sl

buildUnaryOperatorSubtree :: Operator -> Node -> Node
buildUnaryOperatorSubtree a x = 
    Tree $ Subtree ( Operator a ) [ x ]

setPriorityInOperatorTree :: Int -> Node -> Node
setPriorityInOperatorTree i ( Tree ( Subtree ( Operator ( Op a _ x ) ) y ) ) =
    Tree $ Subtree ( Operator $ Op a i x ) y

setPriorityInOperatorTree _ x = x

Функция buildTopTree проверяет, является ли ее аргумент, представленный типом Node, листом, если это так, то она возвращает простое поддерево (Subtree) с корнем - оператором типа Top и единственным листом - переданным ей аргументом, если же аргумент - дерево, то buildTopTree возвращает его представление типа Subtree. Функция buildOperatorSubtree  и вспомогательные функции getDeepestLeft и moveDownLeft строят поддерево для бинарных операторов и сдвигают лево-ассоциативные операторы (т.е. все бинарные операторы) вправо (т.е. вглубь дерева) относительно операторов с таким же приоритетом: это позволяет исправить правоассоциативные правила грамматики для левоассоциативных операторов. Функция setPriorityInOperatorTree позволяет избежать порчи дерева при сдвиге левоассоциативных операторов для выражений, содержащихся в скобках. Функции buildFunction1Subtree и buildUnaryOperatorSubtree довольно простые и делают то, что от них требует их название.
Это практически все. Осталось упомянуть, что тестовые примеры я поместил в файл cf.hs, а компиляция программы основана на использовании Makefile, поэтому достаточно только распаковать пример и запустить команду make.

Кроме того, хотелось бы сказать несколько слов о сравнительной производительности программ, написанных с использованием boost::spirit и haskell / happy. Я промолчу о скорости компиляции: итак всем понятно, насколько долго будет компилироваться код на C++, использующий шаблонные объявления из boost::spirit. Меня намного больше удивила разница в скорости выполнения откомпилированных программ. Для корректности сравнения я убрал эвалюацию синтаксических деревьев из кода на boost::spirit. Так вот, код на haskell / happy выполнялся на моем компьютере (двухъядерный AMD 64) в среднем порядка 0.04 секунды, код на boost::spirit с включенной оптимизацией -O2: порядка 0.35 сек. (в 10 раз дольше!), а без оптимизации - вообще 3.4 сек., т.е. примерно в 100 раз дольше!

Исходный код примера можно взять здесь.

Обновление примера грамматики с boost::spirit

Обновил пример для грамматики boost::spirit. Порядок построения узлов для бинарных операторов с лево-правой ассоциативностью (т.е. для всех бинарных операторов данной грамматики) был неверен, т.е. в цепочках типа

1 * 2 * 3 / 4

сначала выполнялась операция деления для операндов 3 и 4, затем операция умножения для операнда 2 и результата предыдущей операции и т.д. (на самом деле немного не так, поскольку в исходной версии была предпринята неуклюжая попытка построения правильного дерева, которая, к сожалению, работала только для простых случаев типа 5 * 6 / 7). На данный момент синтаксические деревья для любых сколь угодно сложных выражений парсятся корректно (по крайней мере в тех тестах, которые я написал и добавил в новую версию программы).
Кстати, пока занимался отладкой примера, обнаружил, что python может неверно вычислять арифметические выражения:

$ python
Python 2.6.4 (r264:75706, Jun  4 2010, 18:20:31) 
[GCC 4.4.4 20100503 (Red Hat 4.4.4-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 8 * 4 / ( 2 - 7 ) * 6 / 3
-14
>>>

Или я чего-то не понимаю в питоне, или это какой-то баг. В любом случае непонятно, как можно доверять языку, который неправильно вычисляет арифметические выражения. Может им баг засабмиттить?

Вот ссылка на новую версию программы.

В следующий раз выложу аналогичную программу, реализованную на Haskell, она почти готова.

Update:  зафайлил баг в питон, но мне мягко объяснили в чем моя ошибка. Вот дословно комментарий от Mark Dickinson:

It's not a bug:  you're seeing Python's rules for integer division, which do indeed differ from those of (some) other languages when either the divisor or the dividend is negative.  For integers x and y, in Python 2.x, x / y gives the floor of the exact quotient.

>>> -32 / 5
-7
>>> 32 / -5
-7

In Python 3.x, the '/' operator does 'true division', giving you (a floating-point approximation to) the true result:

>>> -32 / 5
-6.4
>>> 32 / -5
-6.4

You can also get this behaviour in Python 2.x if you start your script with 'from __future__ import division'.

See the documentation at:

http://docs.python.org/reference/expressions.html#binary-arithmetic-operations

for more.

В общем, оператор '/' имеет какую-то странную семантику в питоне 2.x

Как записать аудио CD из файлов flac и mp3

Итак, допустим у нас имеется директория с файлами flac или mp3. Для начала нужно создать файлы cdr. В случае с flac:

for i in *.flac ; do flac123 -w "${i/\.flac/.cdr}" "$i" ; done

В случае с mp3 почти то же самое:

for i in *.mp3 ; do mpg123 -s "$i" > "${i/\.mp3/.cdr}" ; done

Затем вставляем болванку CD в привод и вводим в терминале

cdrecord -v speed=8 -swab -pad -audio *.cdr

Если нужно, чтобы треки играли без перерыва, то эта команда изменится на

cdrecord -v speed=8 -swab -pad -audio -dao *.cdr

Важно заметить, что названия треков должны быть отсортированы. Если исходные flac или mp3 файлы были пронумерованы (как это обычно бывает), то треки на CD будут записаны в правильном порядке, если же нет, то нужно вместо *.cdr в последних двух командах подставить список cdr файлов в нужной последовательности.

Приемы визуализации состояния кода под управлением Subversion

Здесь я не буду рассматривать стандартные приемы визуализации типа svn log, svn log -v и т.п. Вместо этого я хотел бы показать несколько скриптов-однострочников, которые можно запустить из командной строки оболочки и которые эффективно отражают состояние рабочей версии кода, управляемого системой контроля версий. Поскольку я чаще всего работаю с Subversion, я выбрал именно эту систему контроля версий, хотя это вовсе не обязательное условие и в принципе эти команды при необходимости могут быть адаптированы под любую другую систему, например CVS. В качестве примера рабочей версии кода я взял свой проект sudokurapid. Итак, переходим к приемам.

1. Самая простая задача. Найти все исходники (например, .cc и .h файлы) в рабочей директории и вывести статистику по количеству строк, слов и символов. В данном случае присутствие какой-либо системы контроля версий вообще не требуется.
   

   $ find . -name '*.cc' -o -name '*.h' | xargs wc | sort -n
      33    60   651 ./sudokuRapidCommon.h
      62   146  1201 ./sudokuRapidQt/main.cc
      66   129  1277 ./sudokuRapidQt/sudokuForm.h
      66   156  1456 ./sudokuRapidQt/sudokuScene.h
     117   272  2684 ./sudokuRapidQt/sudokuCell.h
     167   373  3654 ./sudokuRapid.h
     171   497  4244 ./sudokuRapidConsole/main.cc
     175   603  4738 ./sudokuRapidQt/sudokuScene.cc
     191   499  4377 ./sudokuRapidQt/sudokuForm.cc
     248   781  6609 ./sudokuRapidQt/sudokuCell.cc
     481  1702 14315 ./sudokuRapid.cc
    1777  5218 45206 итого 

2. Вывести список всех ревизий, выделив разными цветами имена отдельных пользователей (в данном проекте только один пользователь lyokha, но допустим, что имеется еще один пользователь someone)

   $ svn log | grep '^r[0-9]' | hl -46 lyokha -47 someone
   r16 | lyokha | 2010-08-17 11:40:36 +0400 (Втр, 17 Авг 2010) | 2 lines
   r15 | lyokha | 2009-03-23 16:22:27 +0300 (Пнд, 23 Мар 2009) | 2 lines
   r14 | lyokha | 2009-03-23 15:16:04 +0300 (Пнд, 23 Мар 2009) | 11 lines
   r13 | lyokha | 2009-02-19 22:00:51 +0300 (Чтв, 19 Фев 2009) | 2 lines
   r12 | lyokha | 2009-02-16 14:39:36 +0300 (Пнд, 16 Фев 2009) | 2 lines
   r11 | lyokha | 2009-02-16 14:23:15 +0300 (Пнд, 16 Фев 2009) | 5 lines
   r10 | lyokha | 2009-02-14 17:28:27 +0300 (Сбт, 14 Фев 2009) | 2 lines
   r9 | lyokha | 2009-02-14 16:04:59 +0300 (Сбт, 14 Фев 2009) | 3 lines
   r8 | lyokha | 2009-02-12 19:45:31 +0300 (Чтв, 12 Фев 2009) | 18 lines
   r7 | lyokha | 2009-02-11 23:27:04 +0300 (Срд, 11 Фев 2009) | 2 lines
   r6 | lyokha | 2009-02-11 22:08:13 +0300 (Срд, 11 Фев 2009) | 13 lines
   r5 | lyokha | 2009-02-07 14:39:56 +0300 (Сбт, 07 Фев 2009) | 2 lines
   r4 | lyokha | 2009-02-06 14:06:17 +0300 (Птн, 06 Фев 2009) | 3 lines
   r3 | lyokha | 2009-02-06 11:31:39 +0300 (Птн, 06 Фев 2009) | 2 lines
   r2 | lyokha | 2009-02-06 11:27:49 +0300 (Птн, 06 Фев 2009) | 2 lines
   r1 | lyokha | 2009-02-05 16:24:32 +0300 (Чтв, 05 Фев 2009) | 2 lines

   
   В данном случае я использовал утилиту hl, которая позволяет подсвечивать разными цветами (46 и 47 - это номера цветов для 256-цветного терминала) шаблоны (lyokha и someone) прямо в терминале. Если бы в списке был пользователь someone, его имя было бы подсвечено другим цветом. 
3. Вывести статистику работы для определенного пользователя (lyokha) в псевдографическом виде. Здесь я использую замечательную утилиту diffstat:

   $ for i in `svn log | grep lyokha | awk '{print $1}' | sed 's/r//'`
   > do svn diff -c$i
   > done | diffstat -m -f 4 -w 80
    ChangeLog                       |   62    62     0     0 ++++
    Makefile.am                     |   41    36     0     5 ++!
    README                          |   37    37     0     0 ++
    configure.ac                    |   77    72     0     5 +++++
    sudokuRapid.cc                  |  539   507    26     6 +++++++++++++++++++++++++++++++++++++--
    sudokuRapid.h                   |  172   169     2     1 ++++++++++++
    sudokuRapidCommon.h             |   33    33     0     0 ++
    sudokuRapidConsole/Makefile.am  |    4     3     0     1 
    sudokuRapidConsole/configure.ac |   23    23     0     0 +
    sudokuRapidConsole/getStat.sh   |   54    54     0     0 ++++
    sudokuRapidConsole/main.cc      |  172   171     0     1 ++++++++++++
    sudokuRapidQt/main.cc           |   63    62     0     1 ++++
    sudokuRapidQt/sudokuCell.cc     |  346   256     8    82 ++++++++++++++++++-!!!!
    sudokuRapidQt/sudokuCell.h      |  138   117     0    21 ++++++++!!
    sudokuRapidQt/sudokuForm.cc     |  274   215    24    35 +++++++++++++++--!
    sudokuRapidQt/sudokuForm.h      |   72    68     2     2 +++++
    sudokuRapidQt/sudokuForm.ui     |   97    97     0     0 +++++++
    sudokuRapidQt/sudokuRapidQt.pro |   16    15     0     1 +
    sudokuRapidQt/sudokuScene.cc    |  205   182     7    16 +++++++++++++-
    sudokuRapidQt/sudokuScene.h     |   71    67     1     3 ++++-
    sudokurapid.spec                |  103    91     3     9 ++++++
    21 files changed, 2337 insertions(+), 73 deletions(-), 189 modifications(!)

   В первом столбце указано имя файла, в следующих - общее количество измененных строк, количество вставленных, удаленных и измененных строк, а также псевдографическая гистограмма активности изменений. Стоит заметить, что количество измененных строк (отмеченных символом !) определяется эвристически на основе анализа отдельных чанков, и поэтому в редких случаях баланс вставленных/удаленных/измененных строк может немного не соответствовать действительности.
   
4. Можно графически визуализировать процесс изменения репозитория во времени с использованием утилиты gource. gource не поддерживает Subversion напрямую, поэтому нам понадобится дополнительный скрипт svn-gource.py. Приготовления включают создание промежуточных файлов:

   svn log --verbose --xml > sudokurapid.log
   svn-gource.py --filter-dirs sudokurapid.log > sudokurapid-gource.log

   После этого запускаем

   gource --log-format custom sudokurapid-gource.log

   откидываемся на спинку кресла и смотрим замечательный фильм. Вот, например, один из кадров:
   
   
   
   

C++ жесткач. Что это значит? :)

Небольшое упражнение. Кто сможет объяснить приведенный ниже код?

typedef int  ( & ( *  fun_t )( void ) )[ 10 ];

int  ( &  fun1( void ) )[ 10 ]
{
    static int  ar[ 10 ];

    return ar;
}


int  main( void )
{
    int ( &  ar1 )[ 10 ]( fun1() );

    fun_t  fun( fun1 );

    int ( &  ar2 )[ 10 ] = fun();
}

Как прикрутить вызов фортрановской функции из интерпретатора CINT

CERN ROOT - программа для анализа больших объемов данных, ориентированная прежде всего на использование в научной среде. Программа обладает широкими возможностями по визуализации данных и имеет встроенный интерпретатор языка C++ CINT. Как известно, в физике до сих пор имеет широкое применение язык программирования FORTRAN, на котором написано значительное количество интересных библиотек. Однажды мой коллега-физик попросил меня помочь разобраться в этом вопросе - ему нужно было вызывать функции фортрановской библиотеки MINUIT (разработанной тоже в CERN) непосредственно из интерпретатора CINT. Благодаря поискам решения этой задачи родился этот пример.
Итак, прежде всего создадим функцию на фортране, которая будет вызываться из CINT. Пусть это будет функция, складывающая два числа, также создадим в ней COMMON блок для того, чтобы иметь возможность поэкспериментировать с изменением глобальных переменных:

       INTEGER FUNCTION SUM( A, B )
       DOUBLE PRECISION GL1
       DOUBLE PRECISION GL2
       INTEGER GL3
       COMMON /GL/ GL1( 1, 2 ), GL2, GL3

       INTEGER A, B
       SUM = A + B
       GL1( 1, 1 ) = 0.1
       GL1( 1, 2 ) = 0.2
       GL2 = 10.89
       GL3 = 8
       RETURN
       END

Разместим этот код в файле Sum.f. Теперь нам нужно создать код на C++, который, во-первых, будет вызывать функцию SUM(), а во-вторых, сможет быть вызван из интерпретатора CINT. Пусть вызов SUM() будет организован в виде функтора (т.е. класса с определенным оператором ()) - это упростит семантику вызова из CINT. Разместим наш код в файлах Sum.h и Sum.c. Это содержимое Sum.h:

#include <iostream>
#include "TObject.h"


extern "C" { extern int  sum_( int*, int* ); }

extern struct  fort_struct { double  a[ 2 ][ 1 ]; double  b; int  c; }  gl_;


class  Sum : public  TObject
{
    public:
        int  operator()( int  a, int  b )
        {
            return sum_( &a, &b );
        }

        void  accessGl( void ) const
        {
            printGl();
            gl_.a[ 0 ][ 0 ] = 34.9;
            gl_.a[ 1 ][ 0 ] = 4.1;
            gl_.b = 0.88;
            gl_.c = 70;
            printGl();
        }

    private:
        void  printGl( void ) const
        {
            std::cout << "gl_ = " << gl_.a[ 0 ][ 0 ] << ", " <<
                         gl_.a[ 1 ][ 0 ] << ", " << gl_.b << ", " << gl_.c <<
                         std::endl;
        }

        ClassDef( Sum, 1 )
};

Это содержимое Sum.c:

#include "Sum.h"

ClassImp( Sum )

Сразу отметим наличие определений ClassDef() и ClassImp() - это то, что позволит сделать из нашего Sum объект, с которым интерпретатору CINT будет комфортно работать.
Теперь замечания по использованию фортрановского кода в коде C++:

1. Фортрановские функции должны связываться с C++ кодом как extern "C", при этом название функции записывается в нижнем регистре (несмотря на то, что в исходном коде оно может быть в верхнем регистре), а в конце добавляется символ _ - именно так компилятор фортрана записывает названия функций в объектном коде. В нашем случае функция SUM() трансформировалась в sum_().
2. Аргументы передаются в фортрановскую функцию через указатели, поэтому функция двух целочисленных аргументов SUM() превратилась в sum_( int*, int* ).
3. Глобальные переменные, объявленные в блоке COMMON, также записываются в нижнем регистре с добавлением символа _. Также обратите пристальное внимание на то, что столбцы и строки многомерных массивов в C++ и фортране меняются местами, так, переменная GL1( 1, 2 ) стала double a[ 2 ][ 1 ] в коде C++.

Исходный код готов, теперь нам нужно создать из него подключаемую библиотеку, ниже приводим содержимое Makefile:

all:
 rootcint -f dict_sum.cxx -c Sum.h
 g++ -fPIC -I$(ROOTSYS)/include/root -c dict_sum.cxx Sum.c
 g77 -fPIC -c Sum.f -o Sum_f.o
 g++ -shared -o Sum.so dict_sum.o Sum.o Sum_f.o

clean:
 rm *.o *.so dict_sum.cxx dict_sum.h

Обратите внимание на использование rootcint. Эта утилита создает вспомогательный код, необходимый для использования Sum в CINT, название файла dict_sum.cxx выбрано произвольно. Фортрановский код компилируется с помощью компилятора g77, но ничто не мешает заменить его на gfortran, если это необходимо. После запуска make создается объект Sum.so, который мы будем загружать в CINT, а затем использовать определенные в нем объекты. Пример сессии ROOT:

root [0] .L Sum.so
root [1] Sum s
root [2] int res = s(2,4)
root [3] .p res
(int)6
root [4] s.accessGl()
gl_ = 0.1, 0.2, 10.89, 8
gl_ = 34.9, 4.1, 0.88, 70
root [5]