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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа на 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 либо в другой интересной мне компании :)