Template

---

## One Scala Method

<small>Seven Years of Rewrites</small>

---

## `.subdomain`

---

## scala-uri

- scala-uri a Scala URL Parser
- Used by
  - Guardian homepage
  - HMRC
- 0.1 released 19 Nov 2012

---

![subdomain issue](static/subdomain-issue.png)

---

## Subdomain · First Implementation

```scala
val hostParts = host.split('.').toVector

def subdomain = hostParts.head
```

- Version `0.3.6`

---

![mic drop](https://media.giphy.com/media/3o7qDSOvfaCO9b3MlO/giphy.gif)

---

## First Implementation · Problems

<br>

```scala
scala> Url.parse("https://google.com").subdomain
res0: String = google

scala> Url.parse("http://127.0.0.1/index.html").subdomain
res1: String = 127

scala> Url.parse("https://console.aws.amazon.com").subdomain
res2: String = console
```

---

class: nord-light, center, middle
 
![dunno](https://media.giphy.com/media/y65VoOlimZaus/giphy.gif)

## What even is a Subdomain?

---

## Subdomain · Definition

> A subdomain is a domain that is part of a larger domain.
> For example, `west.example.com` is a subdomain of the `example.com` domain, 
> which in turn is a subdomain of the `com` top-level domain (TLD).

[Source: wikipedia](https://en.wikipedia.org/wiki/Subdomain)

---

## Subdomain · Being Pragmatic

<br>

- How do we drop the TLD + Domain Name?

---

## Dropping the TLD

```scala
host.split('.').dropRight(2)
```

- What about SLDs `.co.uk`? lower levels?
 - So what's the algorithm?

---

![mild shock](https://media.giphy.com/media/PFwKHjOcIoVUc/giphy.gif)

## There is no algorithm
 
---

## publicsuffix.org

> Since there was and remains no algorithmic method of finding the highest level at 
> which a domain may be registered, the only method is to create a list. 
> This is the aim of the Public Suffix List.

- Maintained by Mozilla Foundation
- Effective top-level domain (eTLD)
- Firefox/Chrome/Chromium/Opera/IE

---

## publicsuffix.org

```sql
// ===BEGIN ICANN DOMAINS===
 
// ac : https://en.wikipedia.org/wiki/.ac
ac
com.ac
edu.ac
gov.ac
net.ac
mil.ac
org.ac
```

- Full List [public_suffix_list.dat](https://github.com/publicsuffix/list/blob/master/public_suffix_list.dat)
 - Find the **longest** match against a list of suffixes

---

## Trie

- Encoding `uk`, `hk`, `co.uk` and `ac.uk`

<br>

.mermaid[
<pre>
  graph LR
    root(( )) --> k((k)) --> u((u)) --> d1((.))
    k --> h((h))
    d1 --> o((o)) --> c1((c))
    d1 --> a((a)) --> c2((c))

style root fill:#444,stroke:#444
    style u fill:#ffdede,stroke:#d33,color:#d33
    style h fill:#ffdede,stroke:#d33,color:#d33
    style c1 fill:#ffdede,stroke:#d33,color:#d33
    style c2 fill:#ffdede,stroke:#d33,color:#d33
</pre>
]

<br>

---

## Trie · In Scala

<br>

<strong>
```scala
case class Trie(
  ‏‏‎ ‎ children: Map[Char,Trie],
‏‏‎‎‏‏‎ ‎ end: Boolean
)
```
</strong>

---

## Trie · By Segment

- Encoding `uk`, `hk`, `co.uk` and `ac.uk`

<br>

.mermaid[
<pre>
  graph LR
    root(( )) --> uk((uk)) --> co((co))
    root --> hk((hk))
    uk --> ac((ac))

style root fill:#444,stroke:#444
    style uk fill:#ffdede,stroke:#d33,color:#d33
    style hk fill:#ffdede,stroke:#d33,color:#d33
    style co fill:#ffdede,stroke:#d33,color:#d33
    style ac fill:#ffdede,stroke:#d33,color:#d33
</pre>
]

<br>

---

## Segment Trie · In Scala

<br>

<strong>
```scala
case class Trie(
  ‏‏‎ ‎ children: Map[String,Trie],
  ‏‏‎ ‎ end: Boolean
)
```
</strong>

---

## Which Trie?

- Memory trade offs
- Fewer hops
- Reverse string vs segment split and reverse
- Benchmarks in a later slide!

---

## Death by JSON

```json
{"c":{"்":{"c":{"ர":{"c":{"ூ":{"c":{"ப":{"c":{"்":{"c":{"ப":{"c":{"க":{"c":{"்":{"c":{"ங":
{"c":{"ி":{"c":{"ச":{"c":{},"e":true}},"e":false}},"e":false}},"e":false}},"e":false}},"e":
false}},"e":false}},"e":false}},"e":false}},"e":false}},"e":false},"ם":{"c":{"ו":{"c":{"ק":
{"c":{},"e":true}},"e":false}},"e":false},"e":{"c":{"e":{"c":{"e":{"c":{"i":{"c":{},"e":true
}},"e":false},".":{"c":{"e":{"c":{"i":{"c":{"f":{"c":{},"e":true}},"e":false}},"e":false},
"u":{"c":{"d":{"c":{"e":{"c":{},"e":true}},"e":false}},"e":false},"m":{"c":{"o":{"c":{"c":{
"c":{".":{"c":{"t":{"c":{"o":{"c":{"p":{"c":{"s":{"c":{"g":{"c":{"o":{"c":{"l":{"c":{"b":{
"c":{},"e":true}},"e":false}},"e":false}},"e":false}},"e":false}},"e":false}},"e":false}},
"e":false}},"e":false}},"e":true}},"e":false}},"e":false},"i":{"c":{"r":{"c":{"p":{"c":{},
"e":true}},"e":false}},"e":false},"v":{"c":{"o":{"c":{"g":{"c":{},"e":true}},"e":false}},"e"
:false},"b":{"c":{"i":{"c":{"l":{"c":{},"e":true}},"e":false}},"e":false},"g":{"c":{"r":{"c"
...
```

- Full JSON [public_suffix_trie.json](https://raw.githubusercontent.com/lemonlabsuk/scala-uri/1.4.x/jvm/src/main/resources/public_suffix_trie.json)
- Version `0.5.0`

---

## Concerns
 
- Introduced a JSON Parsing dependency
- `0.5.x` and `1.x` - no Scala.js support
- [Poor GraalVM experience](https://github.com/lemonlabsuk/scala-uri/issues/22):

![graal vm](static/graal.png)

---

## Code Gen!

- `2.0.0` let's replace that JSON with code

---

## Code Gen?

```sql
[error] Error while emitting io/lemonlabs/uri/inet/PublicSuffixTrie$
[error] Method too large: io/lemonlabs/uri/inet/PublicSuffixTrie$.publicSuffixTrie ()Trie;
[error] one error found
```

---

## Code Gen?

```sql
[error] Error while emitting io/lemonlabs/uri/inet/PublicSuffixTrie$
[error] Class too large: io/lemonlabs/uri/inet/PublicSuffixTrie$
[error] one error found
```

---

## Code Gen

```scala
package io.lemonlabs.uri.inet

object PublicSuffixTrie { 
  ‏‏‎ ‎ lazy val publicSuffixTrie = Trie(Map(
  ‏‏‎ ‎   ''்' -> _bcd.t,'ם' -> _5dd.t,'e' -> _65.t,'л' -> _43b.t,'販' -> _8ca9.t,'团' -> _56e2.t,
  ‏‏‎ ‎   's' -> _73.t,'拿' -> _62ff.t,'्' -> _94d.t,'业' -> _4e1a.t,'你' -> _4f60.t,'б' -> _431.t,
  ‏‏‎ ‎   'x' -> _78.t,'品' -> _54c1.t,'物' -> _7269.t,'و' -> _648.t,'山' -> _5c71.t,'府' -> _5e9c.t,
  ‏‏‎ ‎   '站' -> _7ad9.t,'闻' -> _95fb.t,'ತ' -> _ca4.t,'ب' -> _628.t,'籍' -> _7c4d.t,'益' -> _76ca.t,
  ‏‏‎ ‎   '尚' -> _5c1a.t,'线' -> _7ebf.t,'n' -> _6e.t,'ม' -> _e21.t,'动' -> _52a8.t,'な' -> _306a.t,
  ‏‏‎ ‎   ...
}
```

- 154k lines of Scala code
- Full code [PublicSuffixTrie.scala](https://raw.githubusercontent.com/lemonlabsuk/scala-uri/2.0.0/shared/src/main/scala/io/lemonlabs/uri/inet/PublicSuffixTrie.scala)

---

## It worked!

---

## Another issue

<br>

---

## Let's Benchmark

- Trie (each node a character)
- Trie (each node a segment)
- and???

---

![short circuit scan](https://media.giphy.com/media/DwrnYsZCXspu8/giphy.gif)

## Scan the whole public suffix list

---

## Set look-up

- Store public suffix list in a `Set`
- Lookup suffixes L to R

```scala
suffixes.contains("www.google.co.uk")  false
suffixes.contains("google.co.uk")      false
suffixes.contains("co.uk")             true
```
---

## Benchmarking Public Suffix Algorithms · List Size

---

## Benchmarking Public Suffix Algorithms · Segment Count

---

## Today

- scala-uri `2.2.2`
- `Set` look-ups for public suffixes
- 1.4MB Scala.js build

---

## Thanks!