Software Design by Example: An HTML Validator

class: slide-title

<p>
  <a href="https://third-bit.com/sdxpy/">Software Design by Example</a>
</p>
<h1>An HTML Validator</h1>
<div class="bottom">
  <a href="../">chapter</a>
</div>

---

## The Problem

-   We generate HTML pages to report experiments

-   Want to be sure they have the right structure
    so that people can get information out of them reliably

-   Learning how to do this prepares us for checking code

---

## HTML as Text

-   HTML documents contain <a class="gl-ref" href="../../glossary/#gl:tag" title="The textual marker showing the start and/or end of an element in an HTML document." markdown="1">tags</a> and text

-   An <a class="gl-ref" href="../../glossary/#gl:tag_opening" title="The textual marker showing the start of an element in an HTML document, written `&lt;tag&gt;`. An opening tag may contain attributes." markdown="1">opening tag</a> like `<p>` starts an element

-   A <a class="gl-ref" href="../../glossary/#gl:tag_closing" title="The textual marker showing the end of an element in an HTML document, written `</tag>`." markdown="1">closing tag</a> like `</p>` ends the element

-   If the element is empty,
    we can use a <a class="gl-ref" href="../../glossary/#gl:tag_self_closing" title="A textual marker representing an element in an HTML document that has no content, written `&lt;tag/&gt;`. A self-closing tag may contain attributes." markdown="1">self-closing tag</a> like `<br/>`

-   Opening and self-closing tags can have <a class="gl-ref" href="../../glossary/#gl:attribute" title="A name-value pair associated with an object, used to store metadata about the object such as an array's dimensions." markdown="1">attributes</a>

-   Written as `key="value"` (with some variations)

-   Tags must be properly nested:
    `<a><b></a></b>` is illegal

---

## HTML as a Tree

-   HTML elements form a <a class="gl-ref" href="../../glossary/#gl:tree" title="A graph in which every node except the root has exactly one parent." markdown="1">tree</a> of <a class="gl-ref" href="../../glossary/#gl:node" title="An element of a graph that is connected to other nodes by edges. Nodes typically have data associated with them, such as names or weights." markdown="1">nodes</a> and text

-   The object that represent these make up the <a class="gl-ref" href="../../glossary/#gl:dom" title="A standard, in-memory representation of HTML and XML. Each element is stored as a node in a DOM tree with a set of named attributes; contained elements are child nodes." markdown="1">Document Object Model</a> (DOM)

---

## From Text to DOM

-   Real-world HTML is often messy

-   Use [Beautiful Soup][beautiful_soup] to parse it

-   Nodes are `NavigableString` (for text) or `Tag` (for element)

-   `Tag` nodes have properties `name` and `children`

```py
from bs4 import BeautifulSoup, NavigableString, Tag

doc = BeautifulSoup(text, "html.parser")
display(doc)
```

---

## From Text to DOM

```py
text = """<html>
<body>
<h1>Title</h1>
<p>paragraph</p>
</body>
</html>"""
```

```
node: [document]
node: html
string: '\n'
node: body
string: '\n'
node: h1
string: 'Title'
string: '\n'
node: p
string: 'paragraph'
string: '\n'
string: '\n'
```

---

## Recursion

```py
def display(node):
    if isinstance(node, NavigableString):
        print(f"string: {repr(node.string)}")
        return
    else:
        print(f"node: {node.name}")
        for child in node:
            display(child)
```

-   Text nodes don't have children

-   `for child in node` loops over children of element nodes

---

## Attributes

-   A dictionary `node.attrs`

-   Can be single-valued or multi-valued

```py
def display(node):
    if isinstance(node, Tag):
        print(f"node: {node.name} {node.attrs}")
        for child in node:
            display(child)
```

---

## Attributes

```py
text = """<html lang="en">
<body class="outline narrow">
<p align="left" align="right">paragraph</p>
</body>
</html>"""
```

```
node: [document] {}
node: html {'lang': 'en'}
node: body {'class': ['outline', 'narrow']}
node: p {'align': 'right'}
```

---

## Build a Catalog

-   What kinds of children do elements have?

-   `<tr>` (table row) should only appear inside `<table>` or `<tbody>`

-   Recurse through DOM tree

```py
def recurse(node, catalog):
    assert isinstance(node, Tag)

if node.name not in catalog:
        catalog[node.name] = set()

for child in node:
        if isinstance(child, Tag):
            catalog[node.name].add(child.name)
            recurse(child, catalog)

return catalog
```

---

## Build a Catalog

```html
<html>
  <head>
    <title>Software Design by Example</title>
  </head>
  <body>
    <h1>Main Title</h1>
    <p>introductory paragraph</p>
    <ul>
      <li>first item</li>
      <li>second item is <em>emphasized</em></li>
    </ul>
  </body>
</html>
```

---

## Build a Catalog

```
body: h1, p, ul
em:
h1:
head: title
html: body, head
li: em
p:
title:
ul: li
```

---

## The Visitor Pattern

-   A <a class="gl-ref" href="../../glossary/#gl:visitor_pattern" title="A design pattern in which the operation to be done is taken to each element of a data structure in turn. It is usually implemented by having a generator "visitor" that knows how to reach the structure's elements, which is given a function or method to call for each in turn, and that carries out the specific operation." markdown="1">visitor</a> is a class
    that knows how to get to each element of a data structure

-   Derive a class of our own that does something for those elements

-   When we recurse, allow separate handlers for entry and exit

-   Useful for things like pretty-printers

---

## The Visitor Pattern

```py
class Visitor:
    def visit(self, node):
        if isinstance(node, NavigableString):
            self._text(node)
        elif isinstance(node, Tag):
            self._tag_enter(node)
            for child in node:
                self.visit(child)
            self._tag_exit(node)

def _tag_enter(self, node): pass

def _tag_exit(self, node): pass

def _text(self, node): pass
```

-   `pass` rather than `NotImplementedError`
    because many uses won't need all these methods

---

## Catalog Reimplemented

```py
class Catalog(Visitor):
    def __init__(self):
        super().__init__()
        self.catalog = {}

def _tag_enter(self, node):
        if node.name not in self.catalog:
            self.catalog[node.name] = set()
        for child in node:
            if isinstance(child, Tag):
                self.catalog[node.name].add(child.name)
```

-   Only a few lines shorter than the original

-   But the more complicated the data structure is,
    the more helpful the Visitor pattern becomes

---

## Catalog Reimplemented

```py
with open(sys.argv[1], "r") as reader:
    text = reader.read()
doc = BeautifulSoup(text, "html.parser")

cataloger = Catalog()
cataloger.visit(doc.html)
result = cataloger.catalog

for tag, contents in sorted(result.items()):
    print(f"{tag}: {', '.join(sorted(contents))}")
```

---

## Visitor in Action

---

## Find Style Violations

-   Compare each parent-child combination against a <a class="gl-ref" href="../../glossary/#gl:manifest" title="A list of something's parts or components." markdown="1">manifest</a>

```yml
body:
- section
head:
- title
html:
- body
- head
section:
- h1
- p
- ul
ul:
- li
```

---

## Find Style Violations

```py
class Check(Visitor):
    def __init__(self, manifest):
        self.manifest = manifest
        self.problems = {}

def _tag_enter(self, node):
        actual = {child.name for child in node
                  if isinstance(child, Tag)}
        errors = actual - self.manifest.get(node.name, set())
        if errors:
            errors |= self.problems.get(node.name, set())
            self.problems[node.name] = errors
```

---

## Running the Checker

```py
def read_manifest(filename):
    with open(filename, "r") as reader:
        result = yaml.load(reader, Loader=yaml.FullLoader)
        for key in result:
            result[key] = set(result[key])
        return result

manifest = read_manifest(sys.argv[1])
with open(sys.argv[2], "r") as reader:
    text = reader.read()
doc = BeautifulSoup(text, "html.parser")

checker = Check(manifest)
checker.visit(doc.html)
for key, value in checker.problems.items():
    print(f"{key}: {', '.join(sorted(value))}")
```

---

## Results

```
body: h1, p, ul
li: em
```

-   Because content is supposed to be inside a `section` tag,
    not directly in `body`

-   And we're not supposed to *emphasize* words in lists

---

class: summary

## Summary

[beautiful_soup]: https://beautiful-soup-4.readthedocs.io/