Хабрахабр

Стажировка в JetBrains: Как мне почти удалось попасть на неё

image

Как и многие молодые разработчики, когда появляется желание найти работу/стажировку — я смотрю в сторону крутых IT компаний.

Недавно я попробовал попасть в ряды JetBrains и под катом готов поделиться полученным опытом.

Почему «почти» удалось?

Наверняка сразу у вас встает такой вопрос.

На мой взгляд у меня имеется неплохое резюме с кучей ачивок и хороший скилл, который я день за днем совершенствую последние 8-9 лет.

Я выполнил тестовое задание (и как мне кажется хорошо), ранее посещал офис JB, который благо находится в моем городе, общался с HH и некоторыми разработчиками компании и в итоге получил отказ на стажировку без каких-либо комментариев.

Скорее всего причина таится в том, что на стажировку JetBrains отбирает исключительно студентов, а я на данный момент только выпустился из 11-го и сдаю один за другим экзамены.

Что ж, это повод в течении ещё целого года поднатаскать себя и подать заявку на следующий год.

Разбор тестового задания

Сроки подачи заявок на стажировку и проверки тестовых заданий закончились, а это значит, что все, кто их решил, включая меня — могут выложить разбор этих заданий, чтобы в следующем году любой желающий студент мог перед началом стажировок JB ознакомиться с примерным уровнем заданий, с которыми ему придется столкнуться и в случае чего подтянуть свои знания.

Я подавал заявку на стажировку в команду разработки отладчика корутин для Kotlin.

Задачей этой команды на стажировке у тех, кто на неё попал в этом году будет доработка этой части отладчика и её интеграция с IDE.

Задание было немного ожидаемым — написать отладчик для небольшого ЯП.

Оно не требует каких-либо глубоких знаний теории построения трансляторов и крутого скилла. Я бы не сказал, что оно сложное, скорее наоборот. Я был удивлен, когда решил поискать на github'е по ключевым словам решения моих «конкурентов» и нашел 1-2 более-менее на вид рабочих решения против около 6-7 пустых репозиториев либо с парой кусков кода, после которых люди опустили руки. Но тем не менее, те, кто подают заявку на стажировку по этому направлению, как минимум должны владеть этими основами и без проблем справиться с этим заданием. Если этот пост будут читать люди, которые забросили это задание — не надо в будущем так делать. Возможно я плохо искал, но тем не менее результаты меня не порадовали. В крайнем случае достаточно было посидеть над заданием пару дней и я уверен — вы бы с ним справились.

Сам текст задания

Задача: реализовать пошаговое исполнение кода для тривиального языка программирования Guu.

Как правило, они остаются на ваше усмотрение. Внимание: в описании ниже заведомо опущены некоторые существенные моменты. Если будет совсем непонятно, пишите на (тут почта, которую я решил убрать).

Каждая процедура начинается со строки sub (subname) и завершается объявлением другой процедуры (или концом файла, если процедура в файле последняя). Программа на Guu состоит из набора процедур. Исполнение начинается с sub main.

В начале строки могут встречаться незначимые символы табуляции или пробелы. Тело процедуры – набор инструкций, каждая из которых находится на отдельной строке. Комментариев в Guu нет. Пустые строки игнорируются.

— call (subname) – вызов процедуры. В Guu есть лишь три оператора: — set (varname) (new value) – задание нового целочисленного значения переменной. — print (varname) – печать значения переменной на экран. Вызовы могут быть рекурсивными.

Программа ниже выведет на экран строку a = 2. Переменные в Guu имеют глобальную область видимости.

sub main
set a 1
call foo
print a

sub foo
set a 2

А вот простейшая программа с бесконечной рекурсией:

sub main
call main

При его запуске отладчик должен останавливаться на строчке с первой инструкцией в sub main и ждать команд от пользователя. Необходимо написать пошаговый интерпретатор для Guu. Минимально необходимый набор команд отладчика:

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 — информация для отладчика.

Если он равен nil (null в Pascal), то далее нет инструкций и нужно завершить выполнение кода, либо вернуться по callback стеку. NextOp — указатель на следующую инструкцию.

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; {$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. Код выше не является чем-то сложным, так что его можно оставить без комментариев.

Скрины решенной задачки:

image

image

Вывод информации об ошибках:

image

image

Ссылка на репозиторий моего решения: клац

Итоги

Итогов особо нет. Придется мне посвятить большую часть лета насыщенному отдыху и поиску вуза (ну, на случай если ЕГЭ я сдам хорошо, конечно), вместо двух месяцев работы и обучения в команде JetBrains.

Возможно в следующем году на Хабре появится новый пост, уже описывающий процесс стажировки в JB либо в другой интересной мне компании 🙂

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть