суббота, 12 марта 2011 г.

Завершение всех процессов в подгруппе (на примере Tcl)

Предыстория вопроса такова: решил я привести в порядок старый код, написанный в начале 2000-ых  и реализующий набор программ для физического моделирования экспериментальной установки. Ядро программы было написано на фортране с использованием библиотеки Geant3. В результате компиляции и линковки создавались две версии программы - интерактивная и пакетная (batch).

Для удобства использования программ были написаны интерфейсы на Tcl/Tk: большой интерфейс для работы с конфигурацией, графикой, с возможностью запуска обеих версий программ, и малый, который позволял запускать программу в пакетном режиме, следить за ее статусом с помощью прогрессбара (нужно отметить, что программы моделирования и на современных процессорах могут работать в течении суток, а то и недель), и останавливать ее работу при двойном нажатии на специальную кнопку Kill.

Внутри большого интерфейса интерактивная программа моделирования запускалась с помощью открытия канала на запись tcl-командой open, соответственно управление и выход из нее не составляли труда, например для прерывания выполнения программы достаточно было записать в канал, созданный open, последовательность Ctrl-C, а для выхода - последовательность quit. Малый интерфейс мог запускаться самостоятельно, или из большого интерфейса как фоновый процесс.

Поскольку пакетная программа не имела средств для взаимодействия с пользователем, то малый интерфейс запускал ее не с помощью open, а как активный (foreground) процесс. Архитектура запуска процессов малого интерфейса была такова:
  1. В начале работы интерфейса (практически одновременно):
    • Процесс диалога с прогрессбаром и кнопкой Kill (background). В этом диалоге:
      • Отдельный процесс, считывающий результаты программы моделирования, сохраняемые в файле на диске, интерпретирующий их и посылающий с помощью tcl-команды send команды родительскому процессу для отображения статуса выполнения на прогрессбаре (background). В случае прочтения специальной метки end, сигнализирующей о завершении пакетной программы моделирования, данный процесс посылает с помощью send своему родительскому процессу команду exit и завершается сам - такое развитие событий соответствует нормальному завершению работы программы.
    • Процесс пакетной программы моделирования (foreground)
  2. По завершении работы программы моделирования:
    • Процесс диалога, предоставляющего возможность записи результатов программы в базу данных.
Волшебная кнопка Kill должна по замыслу завершить все процессы, включая родительский - т.е. процесс с малым интерфейсом, по желанию пользователя до завершения работы программы моделирования.

Моим старым решением было удалить все процессы в группе процессов:
catch {exec kill 0}
Эта tcl-команда запускает обычную команду оболочки kill 0, что соответствует посылке сигнала TERM текущей группе процессов. Это решение прекрасно работает в случае, если малый интерфейс запускается из терминала, но, к сожалению, если он был запущен из большого интерфейса, то последний тоже завершается, что не является правильным поведением. Проблема в том, что вся совокупность процессов, запущенная как единая команда из терминала, рассматривается как единая группа процессов. Соответственно, kill 0 убивает все процессы-предки вплоть до того, который был запущен из терминала.

К сожалению, создать новую группу процессов на уровне интерфейса оболочки, похоже, не представляется возможным: функция для установки группы процессов setsid() существует только на уровне языка C.

Следующим вариантом было:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
catch {exec kill -TERM -$ppid}
Здесь ищется pid родительского процесса с помощью обычной команды оболочки ps, команда string trim необходима, т.к. ps форматирует вывод и может предварять pid пробелами. В команде kill -TERM -$ppid формальное указание типа сигнала (-TERM) обязательно, т.к. мы используем отрицательное значение pid. Команда kill с отрицательным pid применяется для посылки сигнала всем процессам в группе процессов, соответствующей pid. Фактически, эта команда ничем не отличается от kill 0, кроме возможности формально указывать некоторую группу процессов, а не текущую, но в нашем случае это неважно. Этот вариант так же хорошо работает, если родительский процесс (малый интерфейс) был запущен из терминала, однако в случае с большим интерфейсом последний не завершается как раньше - на этот раз при нажатии на кнопку Kill  просто ничего не происходит. Дело в том, что при запуске малого интерфейса из большого процесс, соответствующий малому интерфейсу не образует группу, так как он был запущен не из терминала. Соответственно, команда kill -TERM -$ppid завершается аварийно, но, поскольку ее вызов обрамлен командой catch, пользователь не видит вообще никакой реакции.

Следующее решение оказалось окончательным и в итоге завершение пакетных программ нажатием на кнопку Kill заработало и в большом интерфейсе. Идея связана с рекурсивным завершением всех подпроцессов родительского процесса, начиная с нижних, включая подпроцессы процесса, активизировавшего завершение, но исключая его самого. После рассылки сигнала завершения всем указанным подпроцессам, посылается сигнал родительскому процессу, а затем процесс, активизировавший завершение, завершает свою работу с помощью exit. Рекурсивная функция rec_kill() выполняет первую часть алгоритма:
proc rec_kill pid {
    set procs [list]
    foreach x [split [exec ps -o pid,ppid ax | \
                           awk "{if ( \$2 == \"$pid\" ) { print \$1 }}"] \
                     "\n"] {
        lappend procs [string trim $x]
    }
    foreach x $procs {
        rec_kill $x
        if {$x != [pid]} {
            catch {exec kill -TERM $x}
        }
    }
    #puts $procs
}
В первом цикле foreach создается список дочерних процессов процесса-аргумента функции pid. Делается это с помощью следующей команды оболочки:
ps -o pid,ppid -ax | awk "{if ( \$2 == \$pid ) { print \$1 }}"
Во втором цикле происходит рекурсивный вызов rec_kill() самой себя и посылка сигнала завершения всем элементам-процессам, найденным в предыдущем foreach, если те не являются собственным процессом. Pid собственного процесса находится с помощью tcl-команды pid, которая стоит в квадратных скобках (этот синтаксический элемент Tcl называется командной подстановкой), обратите внимание, что эта команда в скобках не имеет никакого отношения к одноименному аргументу функции rec_kill().

Теперь в обработчике двойного клика кнопки Kill нужно выполнить следующее:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
rec_kill $ppid
exec kill -TERM $ppid
exit
После вызова rec_kill() для родительского процесса (который не трогает собственно родительский процесс) посылаем сигнал для завершения родительскому процессу и выходим с помощью exit.

Одно важное замечание. Будьте очень внимательны с удалением родительского процесса. Родительский процесс может завершиться преждевременно и его pid в дочернем процессе изменится (например, станет 1). В нашем случае, если родительским процессом вдруг станет init, то возможны неприятные последствия, такие как неожиданное завершение пользовательской сессии, ввиду последующего каскадного удаления дочерних процессов init.

Update. Еще 2 важных замечания:
Касательно предыдущего замечания: для того чтобы обезопаситься от случайного завершения процесса, неожиданно ставшего родительским, достаточно в дочернем процессе посылать родителю некий пользовательский сигнал вместо TERM, например сигнал USR1, а в родительском процессе (в том, который нужно завершить) определить обработчик для этого сигнала. В Tcl это можно сделать с помощью команды trap из пакета Expect, для подключения которого в начале программы нужно добавить:
package require Expect
Собственно обработчик сигнала USR1:
trap {exit} USR1
Теперь, если родительский процесс завершится по какой-то причине преждевременно, то новый родительский процесс (скорее всего init) будет игнорировать этот сигнал. Однако это не спасает от каскадного удаления его дочерних процессов функцией rec_kill(). В простейшем случае, чтобы обезопаситься от удаления всех процессов сессии, нужно убедиться, что pid родительского процесса не равен 1.

Второе замечание: как было отмечено, родительский процесс (малый интерфейс) запускает по завершении активного процесса (программы моделирования) процесс-диалог для записи результатов в базу данных. Поскольку rec_kill(), которая посылает сигнал завершения программе моделирования вызывается раньше, чем посылка нашего нового сигнала USR1 (или, как раньше, TERM - это не принципиально), то возможен интересный race condition - малый интерфейс может успеть запустить этот процесс-диалог (так как активная задача была завершена, а сам процесс еще нет), а может и не успеть (если планировщик ОС раньше прибьет малый интерфейс после посылки сигнала из дочернего процесса). Чтобы избежать ненужного вызова процесса-диалога, следует сначала убить родительский процесс, а затем вызвать rec_kill() для его подпроцессов. Однако теперь ситуация осложняется тем, что, поскольку rec_kill() определяет дочерние процессы в своем теле, а сигнал завершения уже был послан родительскому процессу, то он может быть уже завершен и нас может ожидать еще один неприятный race condition, при котором rec_kill() не завершит ничего, либо завершит не те процессы. Чтобы избежать такого развития ситуации, нужно получить список дочерних процессов малого интерфейса до посылки ему сигнала USR1. Теперь обработчик двойного клика кнопки Kill будет выглядеть немного неуклюже:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
if {$ppid == 1} {exit}
set procs [list]
foreach x [split [exec ps -o pid,ppid ax | \
                       awk "{if ( \$2 == \"$ppid\" ) { print \$1 }}"] \
                 "\n"] {
    lappend procs [string trim $x]
}
exec kill -USR1 $ppid
foreach x $procs {
    rec_kill $x
    if {$x != [pid]} {
        catch {exec kill -TERM $x}
    }
}
exit
, но эту неуклюжесть легко устранить введением вспомогательных функций.

суббота, 5 февраля 2011 г.

Подсветка в vim на основе тегов ctags (perl скрипт прилагается)

Из серии было и стало (картинки кликабельны):


Итак, наша задача - обеспечить подсветку в vim не только ключевых слов, но, по возможности, всего исходного кода: собственных функций, классов, пространств имен, переменных и т.д. Эта задача хорошо решается в vim-скрипте ctags_highlighting. Как ясно из названия, этот скрипт использует базу данных ctags (строит сам или берет уже готовую). В состав ctags_highlighting входит питоновский скрипт mktypes.py, который проделывает основную работу, главным результатом которой является vim-скрипт со списком групп подсветки, в случае языков C и C++ этот файл будет называться types_c.vim. Группы подсветки в этом файле не являются стандартными, соответственно используемая цветовая схема должна их поддерживать. Автор ctags_highlighting предлагает собственную цветовую схему bandit. При использовании другой цветовой схемы, ей нужно "сообщить" о новых группах подсветки. В разных схемах это делается по-разному. Я использую цветовую схему xterm16. Для того, чтобы xterm16 знала о новых группах подсветки, я добавил в нее следующие определения:
    "my highlight groups for ctags_highlight
    call s:hi( 'Namespace'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Function'    , 'none', 'cyan'      , 'none'      )
    call s:hi( 'DefinedName' , 'none', 'cyan'      , 'none'      )
    call s:hi( 'EnumerationValue'  , 'none', 'cyan'      , 'none'      )
    call s:hi( 'EnumeratorName', 'none', 'cyan'      , 'none'      )
    call s:hi( 'Member'      , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Union'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'GlobalVariable', 'none', 'cyan'      , 'none'      )
    call s:hi( 'LocalVariable', 'none', 'cyan'      , 'none'      )
    call s:hi( 'GlobalConstant', 'none', 'cyan'      , 'none'      )
    call s:hi( 'Conditional' , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Repeat'      , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Label'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Exception'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Operator'    , 'none', 'cyan'      , 'none'      )
    call s:hi( 'PreCondit'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Include'     , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Macro'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'StorageClass', 'none', 'green'     , 'none'      )
    call s:hi( 'Class'       , 'none', 'green'      , 'none'      )
    call s:hi( 'Structure'   , 'none', 'green'      , 'none'      )
    "my highlight groups from after/syntax/c.vim
    call s:hi( 'Delimiter'   , 'none', 'green'      , 'none'      )
    call s:hi( 'Boolean'     , 'none', 'green'      , 'none'      )
    "my ColorColumn highlight
    call s:hi( 'ColorColumn' , 'none', 'none'      , 'cyan'      )
Эти объявления следует разместить где-нибудь среди похожих объявлений в ~/.vim/colors/xterm16.vim. Кроме объявлений, связанных с ctags_highlighting, здесь добавлены группы подсветки для скрипта after/syntax/c.vim, а также подсветка для вертикальной колонки, которая появилась с выходом в vim 7.3 и в xterm16 пока отсутствует. Конкретные цвета (cyan, green и т.д.) здесь не важны, так как я переопределяю их в файле .vimrc:
syntax on
let xterm16_brightness = 'high'
let xterm16_colormap = 'soft'
let xterm16fg_Comment = 'grey'
let xterm16fg_Identifier = '#87ffaf'
let xterm16fg_Namespace = '#df875f'
let xterm16fg_Function = '#87ffaf'
let xterm16fg_Statement = '#87afdf'
let xterm16fg_EnumerationValue = '#5fafdf'
let xterm16fg_EnumeratorName = '#00afdf'
let xterm16fg_GlobalConstant = '#87875f'
let xterm16fg_GlobalVariable = '#87875f'
let xterm16fg_DefinedName = 'purple'
let xterm16fg_LocalVariable = '#00df87'
let xterm16fg_Class = '#afff87'
let xterm16fg_Structure = '#dfffaf'
let xterm16fg_Member = '#00af87'
let xterm16fg_Conditional = '#5fafff'
let xterm16fg_Repeat = '#5fafff'
let xterm16fg_Label = '#5fdfff'
let xterm16fg_Exception = '#ff5f87'
let xterm16fg_PreCondit = '#af5faf'
let xterm16fg_Include = '#df5f00'
let xterm16fg_Macro = 'purple'
let xterm16fg_StorageClass = '#5faf5f'
let xterm16fg_Operator = '#ffafaf'
let xterm16fg_Delimiter = '#5fffdf'
let xterm16fg_Boolean = '#87afdf'
let xterm16bg_ColorColumn = '#949494'
if $DISPLAY != '' && !has('gui_running')
    let xterm16bg_Normal = 'none'
endif
colo xterm16
Теперь для обновления подсветки тегов можно воспользоваться командами, предоставляемыми плагином ctags_highlighting. К сожалению, на мой взгляд, это не самое лучшее решение. И причин тому несколько. Прежде всего, я не хочу хранить файлы типа tags и types_c.vim в рабочей директории. Во-вторых, в ctags_highlighting нет выраженной модульности, в частности, если я работаю с некой библиотекой (или несколькими библиотеками), то хочу, чтобы теги используемой библиотекой и моего рабочего кода были четко разделены. Это позволит быстро перестраивать теги для рабочего кода, не изменяя, а только добавляя в файл подсветки теги из библиотеки. В-третьих, ctags часто ошибается, что приводит к появлению псевдотегов типа const, а также переопределению объявлений используемой библиотеки как локальных переменных рабочего кода (если установлено использование локальных переменных).
Представленный здесь скрипт основан на использовании mktypes.py и призван обойти указанные недостатки. Для просмотра опций достаточно набрать имя скрипта MakeVimHlTags без аргументов. В скрипте используется понятие проекта; проекты расположены в директории ~/opt/tags/. В сущности, проект напрямую соответствует модулям в том смысле, о котором говорилось выше. То есть, если в собственном исходном коде используются библиотеки lib1 и lib2, и есть желание подсветить теги из этих библиотек, то можно создать два проекта lib1 и lib2. Для этого следует перейти в каталоги с исходным кодом этих библиотек и выполнить команды:
MakeVimHlTags -r -e const,true,false -p lib1
и
MakeVimHlTags -r -e const,true,false -p lib2
Скорее всего библиотеки находятся в системных директориях и запускать скрипт придется от рута, поскольку mktypes.py создает временные файлы tags и types_c.vim, которые будут удалены по окончании работы скрипта. К счастью, обновлять теги системных библиотек достаточно только при их обновлении. Опция -r означает, что теги будут искаться во всех поддиректориях, начиная с указанных (или как здесь - с текущей). В опции -e перечислены через запятую теги, которые следует игнорировать. В моем случае ctags пытался переопределить слова const, false и true, поэтому я указал, что их следует игнорировать. Опция -e поддерживает простейшие шаблоны, в которых символ "точка" представляет собой последовательность любых символов кроме пробельных; точка может находиться в начале или конце шаблона. Например шаблон "Lib1." обозначает все теги, которые начинаются с "Lib1". Опция -p указывает название проекта.
Теперь следует создать теги для собственного исходного кода. Пусть наш проект называется Proj и использует библиотеки lib1 и lib2. Для того, чтобы добавить в проект теги из другого проекта используется опция -a:
MakeVimHlTags -r -l -a lib1,lib2 -e Lib1.,Lib2. -p Proj
Опция -l нужна для того, чтобы ctags сгенерировал теги для локальных переменных. Это хорошая идея для собственного кода, но плохая - для кода библиотек, поэтому мы не использовали ее для построения тегов проектов lib1 и lib2. В принципе, в случае с C++, теги для локальных переменных не всегда хороши (в частности, если в коде часто используется инициализация в стиле конструктора), поэтому использовать опцию -l следует с осторожностью. С помощью опции -e мы удаляем все теги, которые начинаются с "Lib1" и "Lib2": поскольку в нашем проекте используются имена из lib1 и lib2, то, особенно если включена опция -l, возможны ложные срабатывания ctags для таких имен.
После выполнения трех команд в директории ~/opt/tags/ появятся 3 новых файла: lib1_c.vim, lib2_c.vim и Proj_c.vim. Эти файлы содержат команды для vim, которые необходимы для подсветки тегов, при этом файл Proj_c.vim будет содержать теги из lib1_c.vim и lib2_c.vim.
Осталось самое простое: сделать так, чтобы при открытии файла из рабочей директории проекта Proj скрипт Proj_c.vim выполнялся автоматически. Для этого в файле .vimrc можно ввести следующую команду:
if (filereadable($HOME . "/opt/tags/Proj_c.vim"))
    autocmd BufRead,BufNewFile */part/of/path/to/Proj/* 
        \ execute 'source' . $HOME . "/opt/tags/Proj_c.vim"
endif
где /part/of/path/to/Proj/ - часть относительного пути к рабочей директории проекта Proj.
Для обновления тегов подсветки достаточно выполнить последнюю приведенную команду MakeVimHlTags, при этом теги проектов lib1 и lib2 не перестраиваются, а просто включаются из готовых файлов.

Скрипт MakeVimHlTags можно взять здесь.

пятница, 28 января 2011 г.

Подсчет числа установленных битов в 9-битовом поле

Задача подсчета установленных битов возникла при разработке библиотеки для решения японской игры судоку. В судоку нужно заполнять клетки цифрами от 1 до 9 так, чтобы ни в одной горизонтальной и вертикальной линиях (поле в игре представлено линиями 9x9 и разбито на 9 квадратов 3x3), а также ни в одном из квадратов, не было одинаковых цифр. С точки зрения алгоритма решения задачи, состояние каждой клетки удобно хранить в 9-битовом поле, где установленными битами помечены "выбывшие" цифры; соответственно поле без установленных битов означает, что в клетку можно вставить любую из 9 цифр, а если, скажем, в поле остался не установленным единственный 6-ой бит, то в эту клетку можно поместить только цифру 6.
Алгоритм подсчета установленных битов в 32-битном слове прекрасно описан в книге Генри Уоррена мл. "Hacker's Delight" (которую по непонятным причинами перевели на русский как "Алгоритмические трюки для программистов"). Алгоритм по своей сути является рекурсивным и основан на методе дихотомии: сначала 32-битное слово делится пополам и задача разбивается на 2 одинаковых подзадачи, в свою очередь, получившиеся 16-битные половинки также делятся пополам, добавляя еще 4 подзадачи, и так происходит до тех пор, пока всё слово не будет разделено на 16 2-битовых полей, в каждом из которых биты подсчитываются 16-ю независимыми подзадачами. Сам автор приводит пример, изображенный на рисунке ниже. Поскольку алгоритм подсчета битов рекурсивен, то его удобней изображать снизу вверх: соответственно нижние 16 подзадач изображены в верхней части рисунка сразу после исходного значения в слове, а итоговый результат находится внизу:
На языке C этот алгоритм можно представить следующим образом:
    x = ( x & 0x55555555 ) + ( ( x >>  1 ) & 0x55555555 );
    x = ( x & 0x33333333 ) + ( ( x >>  2 ) & 0x33333333 );
    x = ( x & 0x0F0F0F0F ) + ( ( x >>  4 ) & 0x0F0F0F0F );
    x = ( x & 0x00FF00FF ) + ( ( x >>  8 ) & 0x00FF00FF );
    x = ( x & 0x0000FFFF ) + ( ( x >> 16 ) & 0x0000FFFF );
В верхнем выражении используется маска 0x55555555, которая в двоичном выражении соответствует циклическому повторению 01; первое слагаемое выделяет биты в этой маске (т.е. все нечетные биты), во втором слагаемом сначала все биты сдвигаются вправо на одну позицию и к полученному значению применяется та же маска (таким образом, выделяются все четные биты). Два полученных значения складываются и результат подобным же образом обрабатывается маской 0x33333333, которая соответствует циклическому повторению 0011. И так далее. Легко видеть, что маски соответствуют "стенкам" битовых полей, характерных для текущего этапа алгоритма дихотомии; "стенки" обозначены на рисунке красными разделителями. Маска подбирается таким образом, чтобы каждое отделение между "стенками" было заполнено ровно наполовину единицами справа и нулями слева.
Наша задача - адаптировать данный алгоритм для 9-битового поля. Для хранения нашего битового поля выберем целочисленный тип с достаточной емкостью (например 8-битный char не подходит), пусть это будет 32-битный int. Пусть наше битовое поле находится в 9 младших битах. Принудительно занулять старшие биты нет необходимости, так как на работу алгоритма они не повлияют.
К сожалению, 9 не делится на 2, поэтому нужно выбрать другое число: 3 - отличный (и единственный) кандидат. 3 в степени 2 и есть 9, соответственно нам понадобятся всего два шага (заметьте, что 2 в пятой степени равно 32, поэтому предыдущий алгоритм выполнялся за 5 шагов). С другой стороны, раз мы поменяли базу с 2 на 3, то вместо двух слагаемых на каждом шаге нам понадобятся 3, что соответствует двум сдвигам битов для выделения по маскам.
Давайте приведем функцию, которая выполняет подсчет:
  int  countSetBits9( int  nmb )
  {
      nmb =  ( nmb & 0x49 ) + ( ( nmb >> 1 ) & 0x49 ) + ( ( nmb >> 2 ) & 0x49 );
      return ( nmb & 0x07 ) + ( ( nmb >> 3 ) & 0x07 ) + ( ( nmb >> 6 ) & 0x07 );
  }
Маска 0x49 соответствуе двоичному числу 001001001, а 0x07 - это 000000111. Маски соответствуют заполнению единицами справа на треть отделений битового поля, разделенных "стенками", характерными для двух этапов алгоритма.

среда, 26 января 2011 г.

Простейший пример шаблонного метапрограммирования в C++

Под метапрограммированием обычно понимают предоставление специальных средств внутри или снаружи исходного кода, которые позволяют выводить часть программы автоматически. Таким спецсредством в C++ являются шаблоны (templates). Шаблоны C++ обеспечивают особый метаязык, по своим характеристикам являющийся функциональным и понимаемый исключительно компилятором C++. С функциональными языками шаблонный метаязык сближают наличие общих подходов (сопоставление с образцом, рекурсия) и запрет переменных-состояний.
Рассмотрим следующую ситуацию. Допустим мы хотим создать класс, услуги которого базируются на сходных по назначению, но отличных в их реализации классах BaseA и BaseB. Если оба базовых класса обладают схожим интерфейсом, то логично оформить наш класс в виде шаблона:
    template  < typename  Base >
    class  Derived  : public Base
    {
    };
(Я не буду заострять внимание на содержимом классов, поэтому наш класс пустой, хотя фактически он может содержать множество полей и методов.)
Подразумевается, что вместо шаблонного аргумента Base нужно будет подставлять BaseA либо BaseB в зависимости от требований разработчика. А теперь главный вопрос: что если разработчику необходима информация о базовых классах объектов, основанных на шаблоне Derived. Как ее получить?
На вскидку я могу перечислить четыре способа:
  1. Вполне возможно, что классы BaseA и BaseB сами предоставляют информацию о своих типах. Но это не всегда так, а изменять эти классы мы не можем.
  2. Использование RTTI и dynamic_cast. Во-первых, это не всегда доступно, ведь для использования dynamic_cast необходимо, чтобы BaseA и BaseB были полиморфными, т.е. содержали виртуальные функции. Во-вторых, использование RTTI чревато потерей эффективности.
Оставшиеся два способа связаны с введением в шаблон класса Derived нового метода GetBaseClass(), предоставляющего информацию о базовом типе:
    template  < typename  Base >
    class  Derived : public Base
    {
        public:
            BaseClass  GetBaseClass( void ) const;
    };
BaseClass - это enum, перечисляющий базовые классы, а также значение Prohibited:
    enum  BaseClass
    {
        Prohibited,
        BaseClassA,
        BaseClassB
    };
Итак, оставшиеся способы:
  1. Специализация шаблона Derived для отдельных типов базового класса. К сожалению, шаблон класса Derived может содержать большое число полей и методов, его полная специализация приведет к нежелательному дублированию кода.
  2. Использование трюка, основанного на шаблонном метапрограммировании.
Четвертый способ - это и есть то, что я хотел здесь показать. Он основан на введении вспомогательного шаблона класса (или структуры) BaseClassInstance, не содержащего ничего, кроме статической константы типа BaseClass, и специализированного для разных фактических типов базовых классов:
    template  < typename >
    struct  BaseClassInstance
    {
        static const BaseClass  value = Prohibited;
    };


    template  <>
    struct  BaseClassInstance< BaseA >
    {
        static const BaseClass  value = BaseClassA;
    };


    template  <>
    struct  BaseClassInstance< BaseB >
    {
        static const BaseClass  value = BaseClassB;
    };
(В первом определении после ключевого слова typename можно было указать имя аргумента, например Base, но, поскольку оно не используется в теле шаблона, я его опустил.)
Несмотря на то, что по форме здесь перечисляются разные специализации шаблона структуры C++, по сути, если рассматривать это с точки зрения функционального программирования, здесь объявлены клозы простейшей функции, возвращающей значение типа BaseClass в зависимости от результата сопоставления с образцом (типом - шаблонным аргументом)!
Нам осталось написать тело метода GetBaseClass():
    template  < typename  Base >
    BaseClass Derived< Base >::GetBaseClass( void ) const
    {
        return BaseClassInstance< Base >::value;
    }
Теперь объекты классов, основанных на шаблоне Derived, обладают информацией о своем базовом классе. Эта информация закладывается в момент инстанцирования классов, а значит нет дополнительных нагрузок в ран-тайме, и, что не менее важно, нам не пришлось дублировать исходный код.

пятница, 31 декабря 2010 г.

Чиним 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, когда его допилят.

воскресенье, 19 декабря 2010 г.

Вышел 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), который позволяет пересчитывать уже имеющиеся данные с параметрами, отличными от исходных
Документацию по установке и использованию программы можно найти здесь.

четверг, 9 декабря 2010 г.

Реорганизация структуры репозитория 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: Обязательно делайте бекап репозитория перед какими-либо изменениями внутри него. Также неплохо сохранять копию дампа репозитория до тех пор, пока вы не осознали до конца, что все изменения прошли успешно.