Паяци от Марс

В третото домашно ще си имплементираме паяче, което броди по всеобхватния Web, започвайки от зададена му страница и продължавайки по нейните линкове.

Ще се възползваме от това, че нашият паяк има много крака, за да имплементираме това бродене конкурентно и паралелно, използвайки Future. След като страницата бъде извлечена, ще я предадем на процесор, който да я обработи по определен начин (отново конкурентно) и който ще ни генерира резултат за тази страница. Накрая моноидно ще съберем всички резултати от всички страници.

С какво разполагаме

HTTP е синхронен request -> response протокол, което перфектно пасва на модела на Future-ите. Всеки response на заявка към определен URL (или по-точно, към определен ресурс), се състои от:

• status код, изразяващ резултата от обработката на заявката,
• списък от header-и под формата на ключ -> стойност, описващи response-а,
• тяло, съдържащ резултатно съобщение, например заявената web страница.

Това ще описваме чрез следния тип:

trait HttpResponse {
  def status: Int
  def headers: Map[String, String]
  def bodyAsBytes: Array[Byte]

  def body: String = ...

  def contentType: Option[ContentType] = ...

  def isSuccess: Boolean = 200 <= status && status < 300
  def isClientError: Boolean = 400 <= status && status < 500
  def isServerError: Boolean = 500 <= status && status < 600
}

Status кода е число между 100 и 599, като всеки си има различен смисъл и са подредени по категории. Дефинирали сме проверка за три от категориите – дали е статус за успех, статус за клиентска грешка или статус за сървърна грешка. Най-често успех се обозначава чрез 200.

Тялото представяме чрез масив от байтове, но за улеснение, в случаите когато очакваме то да е текст, сме имплементирали метод body, който превръща байтовете към низ

Един специален header, за който сме създали специален тип, е Content-Type:

case class ContentType(mimeType: String, charset: Option[Charset])

Ако е зададен, той съдържа типа на съобщението, съдържащо се в body-то (HTML, PNG картинка, текст и т.н.) и символна кодировка, ако то е текстово. В companion обекта на ContentType сме описали MIME типа на HTML (text/html) и текстовите документи.

Един HTTP клиент, който поддържа единствено извличане на HTTP ресурси, изглежда по следния начин:

trait HttpClient {
  def get(url: String): Future[HttpResponse]
}

Предоставили сме ви имплементация на такъв клиент чрез библиотеката async-http-client в класа AsyncHttpClient. Характерното за него е, че той имплементира така наречения reactor pattern, който ни позволява да използваме неблокиращ вход/изход, с което една нишка може да се грижи за множествено мрежови комуникации без да бъде блокирана.

get методът извършва заявка към съответния ресурс и връща Future с получения response.

В math пакета може да откриете имплементацията на моноид, която постигнахме по време на лекциите.

Имплементация на web паяк (3 точки)

В Spidey.scala ще намерите следното:

case class SpideyConfig(maxDepth: Int,
                        sameDomainOnly: Boolean = true,
                        tolerateErrors: Boolean = true,
                        retriesOnError: Int = 0)

class Spidey(httpClient: HttpClient)(implicit ex: ExecutionContext) {
  def crawl[O : Monoid](url: String, config: SpideyConfig)
                       (processor: Processor[O]): Future[O] = ???
}

Вашата първа и основна задача е да имплементирате методът crawl. Той има множествено входни параметри/конфигурации, затова помислете добре как ще разбиете имплементацията му на малки части.

SpideyConfig осигурява конфигурационни параметри за начина на работа на crawl, но за основната имплементацията ще се съсредоточим само върху maxDepth, останалите ще разгледаме като допълнение по-късно.

Целта на crawl е да обходи всички линкнати ресурси, започвайки от url и стигайки до дълбочина maxDepth линка от него, да изпрати HttpResponse-а, получен от всеки от тях, към подадения процесор, и да комбинира (слее) резултати от тип O, генерирани от всяко извикване на процесора.

Процесорите имат следния интерфейс:

trait Processor[O] {
  def apply(url: String, response: HttpResponse): Future[O]
}

Пълните изисквания към crawl са следните:

• Първият ресурс, който извлича, е url. Той е на дълбочина 0 от себе си, всички негови линкове са на дълбочинно ниво 1, всички тяхни на 2 и т.н.

• Ще обработваме само HTTP линковете. За да проверите дали даден линк е валиден HTTP линк използвайте HttpUtils.isValidHttp.

• Всеки един ресурс трябва да бъде извлечен най-много веднъж, тоест ако вече е бил срещнат на по-ранно ниво да не се повтаря неговото извличане. За да постигнем това лесно чрез Future ще искаме да имаме конкурентност в извличането и обработването на ресурсите само в едно и също дълбочинно ниво. Тоест първо извличваме и обработваме url, след това всички адреси/ресурси на ниво 1, след като те са готови, всички на ниво 2 (без тези, които вече са били обработени на ниво 0 или 1), и т.н. Това жертва конкурентността в определени моменти (например една много бавна заяка би отложила минаването към обработка към следващото ниво), но пълна конкурентност би изисквала допълнителна синхронизация с други примитиви (като например AtomicReference или актьор).

• Ще обработваме всички типове ресурси, но ще извличаме линкове само от HTML ресурсите. За да извлечете всички линкове от HTML страница използвайте HtmlUtils.linksOf. За всички останали типове считаме, че не съдържат линкове.

• Обработката на HttpResponse от процесор започва веднага щом response-ът бъде получен.

• Всяко извикване на apply на процесор генерира резултат от тип O, който е моноиден. Резултатът от crawl трябва да е моноидното събиране на всички обекти от тип O, като редът, в който ще бъдат събрани, трябва да съвпада с реда, върнат от HtmlUtils.linksOf. Използвайте методът на List distinct за премахване на повторенията.

  Като пример, един възможен процесор може да брои честотата на всяка дума в страницата. Тогава типът O ще бъде WordCount, който на всяка дума съпоставя бройка. Крайнитът резултът от crawl ще бъде честотата на всяка от срещнатите думи във всички посетени страници.

Съвет: Помислете за помощен тип, в който да съхранявате резултатите от обработката на даден URL, докато чакате обработката на останалите.

Допълнения към crawl (1,5 точки)

crawl може допълнително да бъде настройвано със следните параметри:

• sameDomainOnly – ако е true, то се следват само линкове към същия домейн като url. Използвайте HttpUtils.sameDomain за да проверите дали два URL-а имат един и същи домейн.
• tolerateErrors – при стойност false първият fail-нал Future в цялата композиция на crawl трябва да доведе до fail резултат от crawl със същата грешка. При стойност true, при fail, независимо дали от HttpClient.get или processor.apply, считаме, че за този ресурс сме получили моноидна нула (identity на моноид) и че той няма никакви линкове и не прекъсваме изчислението на останалите ресурси.
• retriesOnError – ако е по-голямо от 0, то при fail на Future-а от HttpClient.get или при негов успех, но със status код, който е server error (между 500 и 599), автоматично опитваме отново да извършим request-а чрез повторно извикване на HttpClient.get. Това повтаряме до успех или до най-много retriesOnError пъти. При краен неуспех връщаме резултатът на HttpClient.get от последния retry.

Процесори (1,5 точки)

Последната стъпка е имплементирането на самите процесори, които обработват уеб страниците/ресурсите. Всеки процесор генерира определен тип. За всеки от тях трябва да реализирате и моноидната имлементация на този тип. Ще искаме от вас да създадете три процесора:

WordCounter

WordCounter генерира резултат от тип WordCount, съпоставящ всяка дума на брой срещания.

За успешните response-и (status код между 200 и 299), които са HTML страници (text/html) или страници с чист текст (text/plain), ще искаме да преброим колко пъти се среща всяка дума в тях. За да извлечете текста от HTML документ използайте HtmlUtils.toText. За да вземете списък от всички думи в даден текст използвайте WordCount.wordsOf.

За неуспешните response-и връщайте WordCount с празен map.

FileOutput

FileOutput записва ресурса във файл с уникално-генерирано име, ако response-ът е бил успешен. Резултатният тип е SavedFiles, който съпоставя за всеки файл къде по файловата система и бил записан. Очевидно, едно извикване на apply ще генерира SavedFiles с най-много един елемент в своя map.

FileOutput прима targetDir за това къде да бъдат записвани файловете. Името на файл за определен URL може да генерирате чрез generatePathFor.

За да извършите самото записване използвайте Java функцията Files.write. Извикването на тази функция блокира текущата нишка докато резултатът не бъде записан успешно на файловата система. Практика е операциите, които блокират нишки, или които се изпълняват продължително време, да бъдат стартирани върху създаден за тях отделен pool от нишки, за да не пречат на другите асинхронни операции. Затова FileOutput приема и ExecutionContext, в който да бъде извършено записването.

BrokenLinkDetector

BrokenLinkDetector генерира списък от всички URL-и, за които сме получили отговор със статус код 404 (Not Found). Така можем да намерим всички счупени линкове на даден сайт.

Command-line паяк

Тази част няма да оценяваме, но е добро упражнение за вас да тествате това, което сте реализирали.

В SpideyApp сме започнали имплементацията на приложение, което приема настройки от потребителя и изпълнява някой от реализираните процесори върху зададен URL и неговите линкове. Като упражнение може да опитате да реализирате приложението, загатното в текста на printUsage.

Забележете, че създаваме два ExecutionContext-а – един default-тен и един, които да бъде използван за FileOutput.

Аргументите към приложението се подават на args масива на main. За да изпълните приложението и да ги подадете имате няколко варианта:

• Ако изполвате IntelliJ IDEA от Run -> Edit Configurations може да зададете Program arguments за SpideyApp

• може да стартирате приложението през sbt с sbt "run <аргументи>" (или директно run <аргументи>, ако сте вече в sbt)

• Може да използвате sbt plugin-а assembly, който създава изпълним .jar файл чрез sbt assembly. В project/plugins.sbt може да видите как сме го добавили към текущия проект. Генерираният .jar се появява в target/scala-2.12 и може да се изпълни чрез:

  java -jar target/scala-2.12/spiders-from-mars-assembly-0.1.jar <аргументи>

Тестове (бонус 2 точки)

За да тествате Future-ите имате няколко възможни подхода

1. Да изполвате Await.result във вашите тестове, който блокира нишката на теста докато не се върне резултат, след което да проверите дали резултатът е очакваният.
2. Да използвате ScalaFutures разширенията към ScalaTest.
3. Да използвате async разширенията към ScalaTest

Препоръчваме ви 2 или 3. За подходящи тестове на имплементираната от вас функционалност ще ви дадем до 2 бонус точки.

Оценяване

В това домашно отново ще следим за стил.

Общият брой точки от него е 6 (или 8 с бонус точките).