Как и многие молодые разработчики, когда появляется желание найти работу/стажировку — я смотрю в сторону крутых IT компаний.
Недавно я попробовал попасть в ряды JetBrains и под катом готов поделиться полученным опытом.
Почему «почти» удалось?
Наверняка сразу у вас встает такой вопрос.
На мой взгляд у меня имеется неплохое резюме с кучей ачивок и хороший скилл, который я день за днем совершенствую последние 8-9 лет.
Я выполнил тестовое задание (и как мне кажется хорошо), ранее посещал офис JB, который благо находится в моем городе, общался с HH и некоторыми разработчиками компании и в итоге получил отказ на стажировку без каких-либо комментариев.
Скорее всего причина таится в том, что на стажировку JetBrains отбирает исключительно студентов, а я на данный момент только выпустился из 11-го и сдаю один за другим экзамены.
Что ж, это повод в течении ещё целого года поднатаскать себя и подать заявку на следующий год.
Разбор тестового задания
Сроки подачи заявок на стажировку и проверки тестовых заданий закончились, а это значит, что все, кто их решил, включая меня — могут выложить разбор этих заданий, чтобы в следующем году любой желающий студент мог перед началом стажировок JB ознакомиться с примерным уровнем заданий, с которыми ему придется столкнуться и в случае чего подтянуть свои знания.
Я подавал заявку на стажировку в команду разработки отладчика корутин для Kotlin.
Задачей этой команды на стажировке у тех, кто на неё попал в этом году будет доработка этой части отладчика и её интеграция с IDE.
Задание было немного ожидаемым — написать отладчик для небольшого ЯП.
Я бы не сказал, что оно сложное, скорее наоборот. Оно не требует каких-либо глубоких знаний теории построения трансляторов и крутого скилла. Но тем не менее, те, кто подают заявку на стажировку по этому направлению, как минимум должны владеть этими основами и без проблем справиться с этим заданием. Я был удивлен, когда решил поискать на github'е по ключевым словам решения моих «конкурентов» и нашел 1-2 более-менее на вид рабочих решения против около 6-7 пустых репозиториев либо с парой кусков кода, после которых люди опустили руки. Возможно я плохо искал, но тем не менее результаты меня не порадовали. Если этот пост будут читать люди, которые забросили это задание — не надо в будущем так делать. В крайнем случае достаточно было посидеть над заданием пару дней и я уверен — вы бы с ним справились.
Внимание: в описании ниже заведомо опущены некоторые существенные моменты. Как правило, они остаются на ваше усмотрение. Если будет совсем непонятно, пишите на (тут почта, которую я решил убрать).
Программа на Guu состоит из набора процедур. Каждая процедура начинается со строки sub (subname) и завершается объявлением другой процедуры (или концом файла, если процедура в файле последняя). Исполнение начинается с sub main.
Тело процедуры – набор инструкций, каждая из которых находится на отдельной строке. В начале строки могут встречаться незначимые символы табуляции или пробелы. Пустые строки игнорируются. Комментариев в Guu нет.
В Guu есть лишь три оператора: — set (varname) (new value) – задание нового целочисленного значения переменной. — call (subname) – вызов процедуры. Вызовы могут быть рекурсивными. — print (varname) – печать значения переменной на экран.
Переменные в Guu имеют глобальную область видимости. Программа ниже выведет на экран строку a = 2.
sub main
set a 1
call foo
print a
sub foo
set a 2
А вот простейшая программа с бесконечной рекурсией:
sub main
call main
Необходимо написать пошаговый интерпретатор для Guu. При его запуске отладчик должен останавливаться на строчке с первой инструкцией в sub main и ждать команд от пользователя. Минимально необходимый набор команд отладчика:
i – step into, отладчик заходит внутрь call (subname).
o – step over, отладчик не заходит внутрь call.
trace – печать stack trace исполнения с номерами строк, начиная с main…
var – печать значений всех объявлённых переменных.
Формат общения пользователя с отладчиком остаётся на выше усмотрение. Вы можете выбрать как минималистичный GDB-like интерфейс, так и консольный или графический UI. Названия команд отладчика можно при желании изменить.
Для решения этой задачи вы можете использовать любой язык программирования из TIOBE TOP 50 и open-source компилятором/интерпретатором.
При оценке работы будет оцениваться:
Общая работоспособность программы;
Качество исходного кода и наличие тестов;
Простота расширения функциональности (например, поддержка новых операторов языка или инструкций отладчика).
Решение с инструкцией по его сборке нужно опубликовать в Git-репозиторий (например, на GitHub или BitBucket). В ответе нужно указать ссылку на репозиторий. Подойдёт и ссылка на приватный GitHub-репозиторий, только в него потребуется добавить меня.
Я пишу на C++, Java и Object Pascal.
Сначала были мысли написать все на моем же ЯП (Mash), но я подумал, что это будет не очень удобно проверять сотруднику JB, да и заявку я подал за 2 дня до закрытия подачи (экзамены все-же...), да и за окном уже был вечер — решил я все быстренько написать на более известных языках.
Для решения задачи Pascal на мой взгляд подходит больше всего, как минимум из-за наиболее удобной реализации строк…
По крайней мере для меня. К тому же он находится в TIOBE TOP 50, так что я смело запустил IDE, а именно — Lazarus, т.к. он не коммерческий :) и приступил к решению задачи.
Несмотря на то, что JB дают аж целых 7 дней, по времени у меня в сумме ушло около часа, а проект получился примерно в 500 строк кода.
С чего начать?
Прежде всего нужно представить, как будет в итоге работать отладка кода.
Нам нужно реализовать пошаговое выполнение кода — значит каждая инструкция должна быть представлена в виде структуры/класса и в общем инструкции должны выглядеть как список этих классов или, как в моей реализации — ссылаться друг на друга образуя последовательность (позже распишу почему я так сделал).
Чтобы получить эту последовательность, нашему отладчику нужно обработать код на предложенном языке, значит нам также нужно реализовать небольшой парсер, а также синтаксический и семантический анализ кода.
Начнем с реализации парсера. Т.к. язык Guu состоит из набора токенов, разделяемых пробелом, то логично первым делом написать небольшой и простой токенайзер:
function GetToken(s: string; tokenNum: word): string;
var
p: word;
begin
s := Trim(s);
s := StringReplace(s, ' ', ' ', [rfReplaceAll]);
while tokenNum > 1 do
begin
p := Pos(' ', s);
if p > 0 then
Delete(s, 1, p)
else
begin
s := '';
break;
end;
dec(tokenNum);
end;
p := Pos(' ', s);
if p > 0 then
Delete(s, p, Length(s));
Result := s;
end;
Далее объявляем enum из токенов:
type
TGuuToken = (opSub, opSet, opCall, opPrint, opUnknown);
const
GuuToken: array[opSub..opPrint] of string = (
'sub', 'set', 'call', 'print'
);
И сам класс инструкции, в которую будем разбирать строки кода:
type
TGuuOp = class
public
OpType : TGuuToken;
OpArgs : TStringList;
OpLine : Cardinal;
OpUnChangedLine: string;
NextOp : TGuuOp;
OpReg : Pointer;
function Step(StepInto: boolean; CallBacks: TList; Trace: TStringList): TGuuOp;
constructor Create(LineNum: Cardinal; Line:string);
destructor Destroy; override;
end;
В OpType будет храниться инструкция, в OpArgs — остальные части конструкции.
OpLine, OpUnChangedLine — информация для отладчика.
NextOp — указатель на следующую инструкцию. Если он равен nil (null в Pascal), то далее нет инструкций и нужно завершить выполнение кода, либо вернуться по callback стеку.
OpReg — небольшой указатель-регистр, который будет использоваться далее для небольшой оптимизации выполнения кода.
После того, как было написано объявление класса — я решил, что наиболее компактным и красивым решением было бы дописать парсер и небольшой синтаксический анализ в его конструкторе, что я дальше и сделал:
constructor TGuuOp.Create(LineNum: Cardinal; Line:string);
(*
* That method parse code line.
*)
var
s: string;
w: word;
begin
inherited Create;
OpArgs := TStringList.Create;
OpLine := LineNum;
OpUnChangedLine := Line;
NextOp := nil;
OpReg := nil;
s := GetToken(Line, 1);
OpType := TGuuToken(AnsiIndexStr(s, GuuToken));
case OpType of
opSub : begin // sub <name>
s := GetToken(Line, 2);
if Length(s) > 0 then
OpArgs.Add(s)
else
begin
writeln('[Syntax error]: Invalid construction "sub" at line ', OpLine, '.');
halt;
end;
if Length(GetToken(Line, 3)) > 0 then
begin
writeln('[Syntax error]: Invalid construction "', Line, '" at line ', OpLine, '.');
halt;
end;
end;
opSet : begin // set <var> <value>
OpArgs.Add(GetToken(Line, 2));
OpArgs.Add(GetToken(Line, 3));
w := 1;
while w < Length(OpArgs[1]) + 1 do
begin
if not (OpArgs[1][w] in ['0'..'9']) then
begin
writeln('[Syntax error]: Invalid variable assigment "', Line, '" at line ', OpLine, '.');
halt;
end;
inc(w);
end;
if (Length(OpArgs[0]) = 0) or (Length(OpArgs[1]) = 0) or
(Length(GetToken(Line, 4)) > 0) then
begin
writeln('[Syntax error]: Invalid construction "', Line, '" at line ', OpLine, '.');
halt;
end
end;
opCall : begin // call <name>
s := GetToken(Line, 2);
if Length(s) > 0 then
OpArgs.Add(s)
else
begin
writeln('[Syntax error]: Invalid construction "call" at line ', OpLine, '.');
halt;
end;
if Length(GetToken(Line, 3)) > 0 then
begin
writeln('[Syntax error]: Invalid construction "', Line, '" at line ', OpLine, '.');
halt;
end;
end;
opPrint: begin // print <var>
s := GetToken(Line, 2);
if Length(s) > 0 then
OpArgs.Add(s)
else
begin
writeln('[Syntax error]: Invalid construction "print" at line ', OpLine, '.');
halt;
end;
if Length(GetToken(Line, 3)) > 0 then
begin
writeln('[Syntax error]: Invalid construction "', Line, '" at line ', OpLine, '.');
halt;
end;
end;
else
begin
writeln('[Syntax error]: Invalid token "', s, '" at line ', OpLine, '.');
halt;
end;
end;
end;
destructor TGuuOp.Destroy;
begin
FreeAndNil(OpArgs);
inherited;
end;
Тут мы по сути проверяем начало конструкции (т.е. первое слово), а затем смотрим на остальные токены и их количество. Если с кодом что-то явно не правильно — выводим ошибку.
В главном куске кода мы просто читаем из файла код в TStringList, построчно вызываем конструкторы TGuuOp и сохраняем указатели на экземпляры классов в GuuOps: TList.
Объявления:
var
LabelNames: TStringList;
GuuOps, GuuVars: TList;
SubMain: TGuuOp = nil;
Совместно с парсингом кода хорошо бы выполнить ещё пару действий:
procedure ParseNext(LineNum: Cardinal; Line: string);
(*
* Parsing code lines and define variables and labels.
*)
var
Op: TGuuOp;
GV: TGuuVar;
c: cardinal;
begin
if Trim(Line) <> '' then
begin
Op := TGuuOp.Create(LineNum, Line);
GuuOps.Add(Op);
case Op.OpType of
opSet: begin // define variable and/or optimisation var calling
GV := nil;
c := 0;
while c < GuuVars.Count do
begin
if TGuuVar(GuuVars[c]).gvName = Op.OpArgs[0] then
begin
GV := TGuuVar(GuuVars[c]);
break;
end;
inc(c);
end;
if GV = nil then
begin
GV := TGuuVar.Create(Op.OpArgs[0]);
GuuVars.Add(GV);
end;
Op.OpReg := GV;
end;
opSub: begin // Check for label dublicade declaration
if Op.OpArgs[0] = 'main' then
SubMain := Op;
if LabelNames.IndexOf(Op.OpArgs[0]) <> -1 then
begin
writeln('[Error]: Dublicate sub "', Op.OpArgs[0], '" declaration at line ', Op.OpLine, '.');
halt;
end
else
LabelNames.Add(Op.OpArgs[0]);
end;
end;
end;
end;
На данном этапе можно проверить точки входа на момент переопределения и вспомнить про OpReg — его я использовал для хранения указателя на Guu переменную.
К слову о переменных — вынес этот небольшой кусок кода в отдельный юнит:
unit uVars;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils;
type
TGuuVar = class
public
gvName: string;
gvVal: variant;
constructor Create(VarName: string);
end;
implementation
constructor TGuuVar.Create(VarName: string);
begin
inherited Create;
gvName := VarName;
gvVal := 0;
end;
end.
Теперь у нас есть распарсенный код, который по синтаксису вроде бы правильный. Осталось его проанализировать и можно приступать к выполнению и самому главному — отладке.
Далее следует реализовать небольшой семантический анализ и попутно подготовить все к выполнению и отладке кода:
procedure CheckSemantic;
(*
* Semantic analyse and calls optimisation.
*)
var
c, x: cardinal;
op: TGuuOp;
begin
if GuuOps.Count > 0 then
begin
if TGuuOp(GuuOps[0]).OpType <> opSub then
begin
writeln('[Error]: Operation outside sub at line ', TGuuOp(GuuOps[0]).OpLine, '.');
halt;
end;
c := 0;
while c < GuuOps.Count do
begin
case TGuuOp(GuuOps[c]).OpType of
opSub:;
opCall: begin
TGuuOp(GuuOps[c - 1]).NextOp := TGuuOp(GuuOps[c]);
x := 0;
op := nil;
while x < GuuOps.Count do
begin
if TGuuOp(GuuOps[x]).OpType = opSub then
if TGuuOp(GuuOps[x]).OpArgs[0] = TGuuOp(GuuOps[c]).OpArgs[0] then
begin
op := TGuuOp(GuuOps[x]);
break;
end;
inc(x);
end;
if op <> nil then
TGuuOp(GuuOps[c]).OpReg := op
else
begin
writeln('[Error]: Calling to not exist sub "', TGuuOp(GuuOps[c]).OpArgs[0],
'" at line ', TGuuOp(GuuOps[c]).OpLine, '.');
halt;
end;
end;
opPrint: begin
TGuuOp(GuuOps[c - 1]).NextOp := TGuuOp(GuuOps[c]);
x := 0;
while x < GuuVars.Count do
begin
if TGuuVar(GuuVars[x]).gvName = TGuuOp(GuuOps[c]).OpArgs[0] then
begin
TGuuOp(GuuOps[c]).OpReg := TGuuVar(GuuVars[x]);
break;
end;
inc(x);
end;
if TGuuOp(GuuOps[c]).OpReg = nil then
begin
writeln('[Error]: Variable "', TGuuOp(GuuOps[c]).OpArgs[0],
'" for print doesn''t exist at line ', TGuuOp(GuuOps[c]).OpLine, '.');
end;
end;
else
TGuuOp(GuuOps[c - 1]).NextOp := TGuuOp(GuuOps[c]);
end;
inc(c);
end;
end;
end;
В TGuuOp.NextOp каждого токена записываем указатель на следующий за ним токен.
Для опкода call делаем все хитро и просто — в NextOp записываем указатель на вызываемую точку входа.
Также проверяем выводимые переменные через инструкцию print…
Может быть их не объявили перед выводом?
Теперь нужно реализовать выполнение кода. Возвращаемся к классу TGuuOp и реализуем метод Step:
function TGuuOp.Step(StepInto: boolean; CallBacks: TList; Trace: TStringList): TGuuOp;
(*
* That method execute instruction.
*)
var
Op: TGuuOp;
CBSize: Cardinal;
begin
case OpType of
opSub: begin
Trace.Add('-> Sub "' + OpArgs[0] + '"');
Result := NextOp;
end;
opCall: begin
if StepInto then
begin
if NextOp <> nil then
CallBacks.Add(NextOp);
Result := TGuuOp(OpReg);
end
else
begin
Op := TGuuOp(OpReg);
CBSize := CallBacks.Count;
while ((Op <> nil) or (CallBacks.Count > CBSize)) and (Trace.Count < STACK_SIZE) do
begin
if Op = nil then
begin
Op := TGuuOp(CallBacks[CallBacks.Count - 1]);
CallBacks.Delete(CallBacks.Count - 1);
Trace.Delete(Trace.Count - 1);
end;
Op := Op.Step(StepInto, CallBacks, Trace);
end;
Result := NextOp;
end;
end;
opPrint: begin
writeln(TGuuVar(OpReg).gvName, ' = ', TGuuVar(OpReg).gvVal);
Result := NextOp;
end;
opSet: begin
TGuuVar(OpReg).gvVal := OpArgs[1];
Result := NextOp;
end;
end;
end;
Чтобы избежать access violation в случае зацикливания — лучше ограничить стек, что я и сделал.
Константа STACK_SIZE = 2048, объявленная выше как раз отвечает за это.
Теперь наконец настало время написать основной код нашего отладчика:
var
code: TStringList;
c: Cardinal;
cmd: string;
CallBacks: TList;
Trace: TStringList;
DebugMode: boolean = true;
begin
if ParamCount > 0 then
begin
// Initialisation
if not FileExists(ParamStr(1)) then
begin
writeln('[Error]: Can''t open file "', ParamStr(1), '".');
halt;
end;
if ParamCount > 1 then
if LowerCase(ParamStr(2)) = '/run' then
DebugMode := false;
code := TStringList.Create;
code.LoadFromFile(ParamStr(1));
GuuOps := TList.Create;
GuuVars := TList.Create;
// Parsing and preparing
LabelNames := TStringList.Create;
c := 0;
while c < code.Count do
begin
ParseNext(c + 1, Trim(code[c]));
inc(c);
end;
FreeAndNil(LabelNames);
CheckSemantic;
if SubMain = nil then
begin
writeln('[Error]: Sub "main" doesn''t exist!');
halt;
end;
// Start code execution
CurrentOp := SubMain;
CallBacks := TList.Create;
Trace := TStringList.Create;
if DebugMode then
begin
//Out code and features
ClrScr;
writeln('Code for debugging:');
writeln('.....');
c := 0;
while c < code.Count do
begin
writeln(FillSpaces(IntToStr(c + 1), 4), '| ', code[c]);
inc(c);
end;
writeln('"""""');
FreeAndNil(code);
writeln(sLineBreak,
'Features:', sLineBreak,
'* i - step into.', sLineBreak,
'* o - step over.', sLineBreak,
'* trace - print stack trace.', sLineBreak,
'* var - print variables list.', sLineBreak,
'* x - exit.', sLineBreak);
// Execution loop
while ((CurrentOp <> nil) or (CallBacks.Count > 0)) and (Trace.Count < STACK_SIZE) do
begin
write('Line ', CurrentOp.OpLine, ' ~> ');
readln(cmd);
// Execute commands
if cmd = 'i' then
CurrentOp := CurrentOp.Step(true, CallBacks, Trace)
else
if cmd = 'o' then
CurrentOp := CurrentOp.Step(false, CallBacks, Trace)
else
if cmd = 'trace' then
begin
writeln('| Trace:');
c := 0;
while c < Trace.Count do
begin
writeln('| ', Trace[c]);
inc(c);
end;
writeln('| -> Line ', CurrentOp.OpLine, ': "', CurrentOp.OpUnChangedLine, '".')
end
else
if cmd = 'var' then
begin
writeln('| Variables list:');
c := 0;
while c < GuuVars.Count do
begin
writeln('| ', TGuuVar(GuuVars[c]).gvName, ' = ', TGuuVar(GuuVars[c]).gvVal);
inc(c);
end;
end
else
if cmd = 'x' then
halt;
// Check for method end & make callback
if (CurrentOp = nil) and (CallBacks.Count > 0) then
begin
CurrentOp := TGuuOp(CallBacks[CallBacks.Count - 1]);
CallBacks.Delete(CallBacks.Count - 1);
Trace.Delete(Trace.Count - 1);
end;
end;
end
else
begin
// Only run mode (/run)
FreeAndNil(code);
while ((CurrentOp <> nil) or (CallBacks.Count > 0)) and (Trace.Count < STACK_SIZE) do
begin
CurrentOp := CurrentOp.Step(false, CallBacks, Trace);
if (CurrentOp = nil) and (CallBacks.Count > 0) then
begin
CurrentOp := TGuuOp(CallBacks[CallBacks.Count - 1]);
CallBacks.Delete(CallBacks.Count - 1);
Trace.Delete(Trace.Count - 1);
end;
end;
end;
if Trace.Count >= STACK_SIZE then
writeln('[Runtime error]: Stack overflow!');
FreeAndNil(CallBacks);
FreeAndNil(Trace);
end
else
writeln(
'Guu debugger v1.0.', sLineBreak,
'Author: Pavel Shiryaev (@RoPi0n).', sLineBreak,
'Run: svmc guu_debugger.vmc <guu source file> [arg]', sLineBreak,
'Args:', sLineBreak,
' /run - Run Guu code.'
);
end.
По условию задания интерфейс можно реализовать как угодно.
Можно было бы реализовать полноценный UI, прикрутить SynEdit к проекту, но на мой взгляд — это пустой труд, который не отразит скилл, да и к тому же, за который не заплатят :)
Так что я ограничился небольшим консольным UI.
Код выше не является чем-то сложным, так что его можно оставить без комментариев. В нем мы берем готовые TGuuOp'сы и вызываем их Step.
Скрины решенной задачки:
Вывод информации об ошибках:
Ссылка на репозиторий моего решения: клац
Итоги
Итогов особо нет. Придется мне посвятить большую часть лета насыщенному отдыху и поиску вуза (ну, на случай если ЕГЭ я сдам хорошо, конечно), вместо двух месяцев работы и обучения в команде JetBrains.
Возможно в следующем году на Хабре появится новый пост, уже описывающий процесс стажировки в JB либо в другой интересной мне компании :)
Автор: Павел
