A computer science degree traditionally includes courses in operating systems, compilers, and databases in order to replace mystery with code. These courses transform Linux, Postgres, and LLVM into improvements, additions, and optimizations to an understandable core architecture. The lesson transcends the specific system studied: all computer systems, no matter how big and seemingly complex, can be studied and understoodOther reasons for these classes: a focus on speed; learning low-level APIs; practice with C; knowing the stack; using systems better; and the importance of the system covered..

But web browsers are still opaque, not just to students but to faculty and industry programmers. This book dissipates this mystery by systematically explaining all major components of a web browser.

Reading this book

Parts 1–3 of this book construct a basic browser weighing in around 1000 lines of code, twice that with the exercises. The average chapter takes 4–6 hours to read, implement, and debug for someone with a few years’ programming experience. Part 4 of this book covers advanced topics; those chapters are longer and have more code.

Your web browser will “work” every step of the way, and every chapter will build upon the last.This idea is from J.R. Wilcox, inspired in turn by S. Zdancewic’s course on compilers. That way, you will also practice growing and improving complex software. If you feel particularly interested in some component, please do flesh it out, complete the exercises, and add missing features. We’ve tried to arrange it so that this doesn’t make later chapters more difficult.

The code in this book uses Python 3, and we recommend you follow along in the same. When the book shows Python command lines, it calls the Python binary python3.A few operating systems use python, but on most that means Python 2. That said, the text avoids dependencies where possible and you can try to follow along in another language. Make sure your language has libraries for TLS connections (Python has one built in), graphics (the text uses Tk), and JavaScript evaluation (the text uses DukPy).

This book’s browser is irreverent toward standards: it handles only a sliver of the full HTML, CSS, and JavaScript languages, mishandles errors, and isn’t resilient to malicious inputs. It is also quite slow. Despite that, its architecture matches that of real browsers, providing insight into those 10 million line of code behemoths.

That said, we’ve tried to explicitly note when the book’s browser simplifies or diverges from standards. And in general, when you’re not sure how your browser should behave in some edge case, fire up your favorite web browser and try it out.

Acknowledgments

We’d like to recognize the countless people who built the web and the various web browsers. They are wonders of the modern world. Thank you! We learned a lot from the books and articles listed in this book’s bibliography—thank you to their authors. And we’re especially grateful to the many contributors to articles on Wikipedia (especially those on historic software, formats, and protocols). We are grateful for this amazing resource, one which in turn was made possible by the very thing this book is about.

Pavel: James R. Wilcox and I dreamed up this course during a late-night chat at ICFP 2018. Max Willsey proof-read and helped sequence the chapters. Zach Tatlock encouraged me to develop the book into a course. And the students of CS 6968 and CS 4962 at the University of Utah found countless errors and suggested important simplifications. I am thankful to all of them. Most of all, I am thankful to my wife Sara, who supported my writing the book, listened to countless status updates, and gave me the strength to finish this many-year-long project.

Chris: I am eternally grateful to my wife Sara for patiently listening to my endless musings about the web, and encouraging me to turn my idea for a browser book into reality. I am also grateful to Dan Gildea for providing feedback on my browser-book concept on multiple occasions. Finally, I’m grateful to Pavel for doing the hard work getting this project off the ground and allowing me to join the adventure. (Turns out Pavel and I had the same idea!)

A final note

This book is, and will remain, a work in progress. Please leave comments and mark typos; the book has built-in feedback tools, which you can enable with Ctrl-E (or Cmd-E on a Mac). The full source code is also available on GitHub, though we prefer to receive comments through the built-in tools.

Why study web browsers? The way I see it, browsers are fundamental to the web, to modern computing, and even to the economy broadly—so it’s worth knowing how they work. And in fact, cool algorithms, tricky data structures, and fundamental concepts come alive inside a web browser. This book walks you through building a browser, from scratch. I hope, as you read it, that you fall in love with web browsers, just like I did.

The browser and me

I—this is Chris speaking—have known the webBroadly defined, the web is the interlinked network (“web”) of web pages on the internet. If you’ve never made a web page, I recommend MDN’s Learn Web Development series, especially the Getting Started guide. This book will be easier to read if you’re familiar with the core technologies. for all of my adult life. Since I first encountered the web and its predecessors,For me, BBS systems over a dial-up modem connection. A BBS is not all that different from a browser if you think of it as a window into dynamic content created somewhere else on the internet. in the early 90s, I’ve been fascinated by browsers and the concept of networked user interfaces. When I surfed the web, even in its earliest form, I felt I was seeing the future of computing. In some ways, the web and I grew together—for example, in 1994, the year the web went commercial, was the same year I started college; while there I spent a fair amount of time surfing it, and by the time I graduated in 1999, the browser had fueled the famous dot-com speculation gold rush. The company for which I now work, Google, is a child of the web and was founded during that time. The web for me is something of a technological companion, and I’ve never been far from it in my studies or work.

In my freshman year at college, I attended a presentation by a RedHat salesman. The presentation was of course aimed at selling RedHat Linux, probably calling it the “operating system of the future” and speculating about the “year of the Linux desktop”. But when asked about challenges RedHat faced, the salesman mentioned not Linux but the web: he said that someone “needs to make a good browser for Linux.”Netscape Navigator was available for Linux at that time, but it wasn’t viewed as especially fast or featureful compared to its implementation on other operating systems. Even back then, in the very first year or so of the web, the browser was already a necessary component of every computer. He even threw out a challenge: “how hard could it be to build a better browser?” Indeed, how hard could it be? What makes it so hard? That question stuck with me for a long time.Meanwhile, the “better Linux browser than Netscape” took a long time to appear….

How hard indeed! After seven years in the trenches working on Chrome, I now know the answer to his question: building a browser is both easy and incredibly hard, both intentional and accidental. And everywhere you look, you see the evolution and history of the web wrapped up in one codebase. But most of all, it’s fun and endlessly interesting.

So that’s how I fell in love with web browsers. Now let me tell you why you will, too.

The web in history

The web is a grand, crazy experiment. It’s natural, nowadays, to watch videos, read news, and connect with friends on the web. That can make the web seem simple and obvious, finished, already built. But the web is neither simple nor obvious. It is the result of experiments and research reaching back to nearly the beginning of computingAnd the web also needed rich computer displays, powerful UI-building libraries, fast networks, and sufficient CPU power and information storage capacity. As so often happens with technology, the web had many similar predecessors, but only took its modern form once all the pieces came together. about how to help people connect and learn from each other.

In the early days, the internet was a world wide network of computers, largely at universities, labs, and major corporations, linked by physical cables and communicating over application-specific protocols. The early web built on this foundation. Web pages were files in a specific format stored on specific computers, and web browsers used a custom protocol to request them. URLs for web pages named the computer and the file, and early servers did little besides read files from a disk. The logical structure of the web mirrored its physical structure.

A lot has changed. HTML is now usually dynamically assembled on the fly“Server-side rendering” is the process of assembling HTML on the server when loading a web page. Server-side rendering often uses web tech like JavaScript, and even a headless browser. Yet one more place browsers are taking over! and sent on demand to your browser. The pieces being assembled are themselves filled with dynamic content—news, inbox contents, and advertisements adjusted to your particular tastes. Even URLs no longer identify a specific computer—content distribution networks route a URL to any of thousands of computers all around the world. At a higher level, most web pages are served not from someone’s home computerPeople actually did this! And when their website became popular, it often ran out of bandwidth or computing power and became inaccessible. but from a social media platform or cloud computing service.

With all that’s changed, some things have stayed the same, the core building blocks that are the essence of the web:

• The web is a network of information linked by hyperlinks.
• Information is requested with the HTTP network protocol and structured with the HTML document format.
• Documents are identified by URLs, not by their content, and may be dynamic.
• Web pages can link to auxiliary assets in different formats, including images, videos, CSS, and JavaScript.
• The user uses a User Agent, called a browser, to navigate the web.
• All these building blocks are open, standardized, and free to use or re-use.

As a philosophical matter, perhaps one or another of these principles is secondary. One could try to distinguish between the networking and rendering aspects of the web. One could abstract linking and networking from the particular choice of protocol and data format. One could ask whether the browser is necessary in theory, or argue that HTTP, URLs, and hyperlinking are the only truly essential parts of the web.

Perhaps.It is indeed true that one or more of the implementation choices could be replaced, and perhaps that will happen over time. For example, JavaScript might eventually be replaced by another language or technology, HTTP by some other protocol, or HTML by its successor. Certainly all of these technologies have been through many versions, but the web has stayed the web. The web is, after all, an experiment; the core technologies evolve and grow. But the web is not an accident; its original design reflects truths not just about computing, but about how human beings can connect and interact. The web not only survived but thrived during the virtualization of hosting and content, specifically due to the elegance and effectiveness of this original design.

The key thing to understand is this grand experiment is not over. The essence of the web will stay, but by studying web browsers you have the chance to contribute and to shape its future.

Real browser codebases

So let me tell you what it’s like to contribute. Some time during my first few months of working on Chrome, I came across the code implementing the <br> tag—look at that, the good-old <br> tag, which I’ve used many times to insert newlines into web pages! And the implementation turns out to be barely any code at all, both in Chrome and in this book’s simple browser.

But Chrome as a whole—its features, speed, security, reliability—wow. Thousands of person-years went into it. There is a constant pressure to do more—to add more features, to improve performance, to keep up with the “web ecosystem”—for the thousands of businesses, millions of developers,I usually prefer “engineer”—hence the title of this book—but “developer” or “web developer” is much more common on the web. One important reason is that anyone can build a web page—not just trained software engineers and computer scientists. “Web developer” also is more inclusive of additional, critical roles like designers, authors, editors, and photographers. A web developer is anyone who makes web pages, regardless of how. and billions of users on the web.

Working on such a codebase can feel daunting. I often find lines of code last touched 15 years ago by someone I’ve never met; or even now discover files and code that I never knew existed; or see lines of code that don’t look necessary, yet seem to be important. How do I understand that 15-year-old code? Or learn the purpose of these new files? Can I delete those lines of code, or are they there for a reason?

Every browser has thousands of unfixed bugs, from the smallest of mistakes to myriad mix ups and mismatches. Every browser must be endlessly tuned and optimized to squeeze out that last bit of performance. Every browser requires painstaking work to continuously refactor the code to reduce its complexity, often through the carefulBrowsers are so performance-sensitive that, in many places, merely the introduction of an abstraction—the function call or branching overhead—has an unacceptable performance cost! introduction of modularization and abstraction.

What makes a browser different from most massive code bases is their urgency. Browsers are nearly as old as any “legacy” codebase, but are not legacy, not abandoned or half-deprecated, not slated for replacement. On the contrary, they are vital to the world’s economy. Browser engineers must therefore fix and improve rather than abandon and replace. And since the character of the web itself is highly decentralized, the use cases met by browsers are to a significant extent not determined by the companies “owning” or “controlling” a particular browser. Other people—you—can contribute ideas and proposals and implementations.

What’s amazing is that, despite the scale and the pace and the complexity, there is still plenty of room to contribute. Every browser today is open-source, which opens up its implementation to the whole community of web developers. Browsers evolve like giant R&D projects, where new ideas are constantly being proposed and tested out. As you would expect, some features fail and some succeed. The ones that succeed end up in specifications and are implemented by other browsers. That means that every web browser is open to contributions—whether fixing bugs or proposing new features or implementing promising optimizations.

And it’s worth contributing, because working on web browsers is a lot of fun.

Browser code concepts

HTML, CSS, HTTP, hyperlinks, and JavaScript—the core of the web—are approachable enough, and if you’ve made a web page before you’ve seen that programming ability is not required. That’s because HTML & CSS are meant to be black boxes—declarative APIs—where one specifies what outcome to achieve, and the browser itself is responsible for figuring out the how to achieve it. Web developers don’t, and mostly can’t, draw their web page’s pixels on their own.

As a black box, the browser is either magical or frustrating (depending on whether it is working correctly or not!). But that also makes a browser a pretty unusual piece of software, with unique challenges, interesting algorithms, and clever optimizations. Browsers are worth studying for the pure pleasure of it.

There are practical reasons for the unusual design of a browser. Yes, developers lose some control and agency—when pixels are wrong, developers cannot fix them directly.Loss of control is not necessarily specific to the web—much of computing these days relies on mountains of other peoples’ code. But they gain the ability to deploy content on the web without worrying about the details, to make that content instantly available on almost every computing device in existence, and to keep it accessible in the future, mostly avoiding the inevitable obsolescence of most software.

What makes that all work is the web browser’s implementations of inversion of control, constraint programming, and declarative programming. The web inverts control, with an intermediary—the browser—handling most of the rendering, and the web developer specifying parameters and content to this intermediary.For example, in HTML there are many built-in form control elements that take care of the various ways the user of a web page can provide input. The developer need only specify parameters such as button names, sizing, and look-and-feel, or JavaScript extension points to handle form submission to the server. The rest of the implementation is taken care of by the browser. Further, these parameters usually take the form of constraints over relative sizes and positions instead of specifying their values directly;Constraint programming is clearest during web page layout, where font and window sizes, desired positions and sizes, and the relative arrangement of widgets is rarely specified directly. A fun question to consider: what does the browser “optimize for” when computing a layout? the browser solves the constraints to find those values. The same idea applies for actions: web pages mostly require that actions take place without specifying when they do. This declarative style means that from the point of view of a developer, changes “apply immediately,” but under the hood, the browser can be lazy and delay applying the changes until they become externally visible, either due to subsequent API calls or because the page has to be displayed to the user.For example, when exactly does the browser compute which CSS styles apply to which HTML elements, after a web page changes those styles? The change is visible to all subsequent API calls, so in that sense it applies “immediately.” But it is better for the browser to delay style re-calculation, avoiding redundant work if styles change twice in quick succession. Maximally exploiting the opportunities afforded by declarative programming makes real-world browsers very complex.

To me, browsers are where algorithms come to life. A browser contains a rendering engine more complex and powerful than any computer game; a full networking stack; clever data structures and parallel programming techniques; a virtual machine, an interpreted language, and a JIT; a world-class security sandbox; and a uniquely dynamic system for storing data.

And the truth is—you use the browser all the time, maybe for reading this book! That makes the algorithms more approachable in a browser than almost anywhere else: the web is already familiar. After all, it’s at the center of modern computing.

The role of the browser

Every year the web expands its reach to more and more of what we do with computers. It now goes far beyond its original use for document-based information sharing: many people now spend their entire day in a browser, not using a single other application! Moreover, desktop applications are now often built and delivered as web apps: web pages loaded by a browser but used like installed applications.Related to the notion of a web app is a Progressive Web App, which is a web app that becomes indistinguishable from a native app through progressive enhancement. Even on mobile devices, apps often embed a browser to render parts of the application UI.The fraction of such “hybrid” apps that are shown via a “web view” is likely increasing over time. In some markets like China, “super-apps” act like a mobile web browser for web-view-based games and widgets. Perhaps in the future both desktop and mobile devices will largely be a container for web apps. Already, browsers are a critical and indispensable part of computing.

So given this centrality, it’s worth knowing how the web works. And in fact, the web is built on simple concepts: open, decentralized, and safe computing; a declarative document model for describing UIs; hyperlinks; and the User Agent model.The User Agent concept views a computer, or software within the computer, as a trusted assistant and advocate of the human user. It’s the browser that makes these concepts real. The browser is the User Agent, but also the mediator of the web’s interactions and the enforcer of its rules. The browser is the implementer of the web: Its sandbox keeps web browsing safe; its algorithms implement the declarative document model; its UI navigates links. Web pages load fast and react smoothly only when the browser is hyper-efficient.

Such lofty goals! How does the browser deliver on them? It’s worth knowing. And the best way to understand that question is to build a web browser.

Browsers and you

This book explains how to build a simple browser, one that can—despite its simplicity—display interesting-looking web pages and support many interesting behaviors.You might relate this to the history of the web and the idea of progressive enhancement. As you’ll see, it’s surprisingly easy, and it demonstrates all the core concepts you need to understand a real-world browser. You’ll see what is easy and what is hard; which algorithms are simple, and which are tricky; what makes a browser fast, and what makes it slow.

The intention is for you to build your own browser as you work through the early chapters. Once it is up and running, there are endless opportunities to improve performance or add features. Many of these exercises are features implemented in real browsers, and I encourage you to try them—adding features is one of the best parts of browser development!

The book then moves on to details and advanced features that flesh out the architecture of a real browser’s rendering engine, based on my experiences with Chrome. After finishing the book, you should be able to dig into the source code of Chromium, Gecko, or WebKit, and understand it without too much trouble.

I hope the book lets you appreciate a browser’s depth, complexity, and power. I hope the book passes along its beauty—its clever algorithms and data structures, its co-evolution with the culture and history of computing, its centrality in our world. But most of all, I hope the book lets you see in yourself someone building the browser of the future.

If you’ve read this far, hopefully you’re convinced that browsers are interesting and important to study. Now we’ll dig a bit into the web itself, where it came from, and how the web and browsers have evolved to date. This history is by no means exhaustive.For example, there is nothing much about SGML or other predecessors to HTML. (Except in this footnote!) Instead, it’ll focus on some key events and ideas that led to the web. These ideas and events will explain how exactly a thing such as the web came to be, as well as the motivations and goals of those who created it and its predecessors.

The Memex concept

The earliest exploration of how computers might revolutionize information is a 1945 essay by Vannevar Bush entitled As We May Think. This essay envisioned a machine called a Memex that helps (think: User Agent) an individual human see and explore all the information in the world. It was described in terms of the microfilm screen technology of the time, but its purpose and concept has some clear similarities to the web as we know it today, even if the user interface and technology details differ.

The web is at its core organized around the Memex-like goal of representing and displaying information, providing a way for humans to effectively learn and explore. The collective knowledge and wisdom of the species long ago exceeded the capacity of a single mind, organization, library, country, culture, group or language. However, while we as humans cannot possibly know even a tiny fraction of what it is possible to know, we can use technology to learn more efficiently than before, and, in particular, to quickly access information we need to learn, remember or recall. Consider this imagined research session described by Vannevar Bush–one that is remarkably similar to how we sometimes use the web:

The owner of the memex, let us say, is interested in the origin and properties of the bow and arrow. […] He has dozens of possibly pertinent books and articles in his memex. First he runs through an encyclopedia, finds an interesting but sketchy article, leaves it projected. Next, in a history, he finds another pertinent item, and ties the two together. Thus he goes, building a trail of many items.

Computers, and the internet, allow us to process and store the information we want. But it is the web that helps us organize and find that information, that knowledge, making it useful.The Google search engine’s well-known mission statement to “organize the world’s information and make it universally accessible and useful” is almost exactly the same. This is not a coincidence—the search engine concept is inherently connected to the web, and was inspired by the web’s design and antecedents.

As We May Think highlighted two features of the memex: information record lookup, and associations between related records. In fact, the essay emphasizes the importance of the latter—we learn by making previously unknown connections between known things:

When data of any sort are placed in storage, they are filed alphabetically or numerically. […] The human mind does not work that way. It operates by association.

By “association”, Bush meant a trail of thought leading from one record to the next via a human-curated link. He imagined not just a universal library, but a universal way to record the results of what we learn. That is what the web can do today.

The web emerges

The concept of hypertext documents linked by hyperlinks was invented in 1964-65 by Project Xanadu, led by Ted Nelson.He was inspired by the long tradition of citation and criticism in academic and literary communities. The Project Xanadu research papers were heavily motivated by this use case. Hypertext is text that is marked up with hyperlinks to other text. A successor called the Hypertext Editing System was the first to introduce the back button, which all browsers now have. (Since the system just had text, the “button” was itself text.)

Hypertext is text that is marked up with hyperlinks to other text. Sounds familiar? A web page is hypertext, and links between web pages are hyperlinks. The format for writing web pages is HTML, which is short for HyperText Markup Language. The protocol for loading web pages is HTTP, which is short for HyperText Transport Protocol.

Independently of Project Xanadu, the first hyperlink system appeared for scrolling within a single document; it was later generalized to linking between multiple documents. And just like those original systems, the web has linking within documents as well as between them. For example, the url “http://example.com/doc.html#link” refers to a document called “doc.html”, specifically to the element with the name “link” within it. Clicking on a link to that URL will load doc.html and scroll to the link element.

This work also formed and inspired one of the key parts of Douglas Engelbart’s mother of all demos, perhaps the most influential technology demonstration in the history of computing. That demo not only showcased the key concepts of the web, but also introduced the computer mouse and graphical user interface, both of which are of course central components of a browser UI.That demo went beyond even this! There are some parts of it that have not yet been realized in any computer system. I highly recommend watching the demo yourself.

There is of course a very direct connection between this research and the document-URL-hyperlink setup of the web, which built on the hypertext idea and applied it in practice. The HyperTIES system, for example, had highlighted hyperlinks and was used to develop the world’s first electronically published academic journal, the 1988 issue of the Communications of the ACM. Tim Berners-Lee cites that 1988 issue as inspiration for the World Wide Web,Nowadays the World Wide Web is called just “the web”, or “the web ecosystem”—ecosystem being another way to capture the same concept as “World Wide”. The original wording lives on in the “www” in many website domain names. in which he joined the link concept with the availability of the internet, thus realizing many of the original goals of all this work from previous decades.Just as the web itself is a realization of previous ambitions and dreams, today we strive to realize the vision laid out by the web. (No, it’s not done yet!)

The word “hyperlink” may have been coined in 1987, in connection with the HyperCard system on Apple computers. This system was also one of the first, or perhaps the first, to introduce the concept of augmenting hypertext with scripts that handle user events like clicks and perform actions that enhance the UI–just like JavaScript on a web page! It also had graphical UI elements, not just text, unlike most predecessors.

In 1989-1990, the first web browser (named “WorldWideWeb”) and web server (named “httpd”, for “HTTP Daemon” according to UNIX naming conventions) were born, written by Tim Berners-Lee. Interestingly, while that browser’s capabilities were in some ways inferior to the browser you will implement in this book,No CSS! in other ways they go beyond the capabilities available even in modern browsers.For example, the first browser included the concept of an index page meant for searching within a site (vestiges of which exist today in the “index.html” convention when a URL path ends in /”), and had a WYSIWYG web page editor (the “contenteditable” HTML attribute and “html()” method on DOM elements have similar semantic behavior, but built-in file saving is gone). Today, the index is replaced with a search engine, and web page editors as a concept are somewhat obsolete due to the highly dynamic nature of today’s web page rendering. On December 20, 1990 the first web page was created. The browser we will implement in this book is easily able to render this web page, even today.Also, as you can see clearly, that web page has not been updated in the meantime, and retains its original aesthetics! In 1991, Berners-Lee advertised his browser and the concept on the alt.hypertext Usenet group.

WorldWideWeb, the first web browser
(Communications of the ACM, August 1994)

Berners-Lee’s Brief History of the Web highlights a number of other key factors that led to the World Wide Web becoming the web we know today. One key factor was its decentralized nature, which he describes as arising from the academic culture of CERN, where he worked. The decentralized nature of the web is a key feature that distinguishes it from many systems that came before or after, and his explanation of it is worth quoting here (highlight is mine):

There was clearly a need for something like Enquire [ed: a predecessor web-like database system, also written by Berners-Lee] but accessible to everyone. I wanted it to scale so that if two people started to use it independently, and later started to work together, they could start linking together their information without making any other changes. This was the concept of the web.

This quote captures one of the key value propositions of the web. The web was successful for several reasons, but I believe it’s primarily the following three:

• It provides a very low-friction way to publish information and applications. There is no gatekeeper to doing anything, and it’s easy for novices to make a simple web page and publish it.

• Once bootstrapped, it builds quickly upon itself via network effects made possible by compatibility between sites and the power of the hyperlink to reinforce this compatibility. Hyperlinks drive traffic between sites, but also into the web from the outside, from sources such as email, social networking, and search engines.

• It is outside the control of any one entity—and kept that way via standards organizations—and therefore not subject to problems of monopoly control or manipulation.

Browsers

The first widely distributed browser may have been ViolaWWW; this browser also pioneered multiple interesting features such as applets and images. This browser was in turn the inspiration for NCSA Mosaic, which launched in 1993. One of the two original authors of Mosaic went on to co-found Netscape, which built Netscape Navigator, the first commercial browser,By commercial I mean built by a for-profit entity. Netscape’s early versions were also not free software—you had to buy them from a store. They cost about $50. which launched in 1994.

The era of the “first browser war” ensued: a competition between Netscape Navigator and Internet Explorer. There were also other browsers with smaller market shares; one notable example is Opera. The WebKit project began in 1999; Safari and Chromium-based browsers, such as Chrome and newer versions of Edge, descend from this codebase. Likewise, the Gecko rendering engine was originally developed by Netscape starting in 1997; the Firefox browser is descended from this codebase. During the first browser war, nearly all of the core features of this book’s simple browser were added, including CSS, DOM, and JavaScript.

The “second browser war”, which according to Wikipedia was 2004-2017, was fought between a variety of browsers, in particular Internet Explorer, Firefox, Safari and Chrome. Chrome split off its rendering engine subsystem into its own code base called Blink in 2013. The second browser war saw the development of many features of the modern web, including widespread use of AJAX requests, HTML5 features like <canvas>, and a huge explosion in third-party JavaScript libraries and frameworks.

Web standards

In parallel with these developments was another, equally important, one—the standardization of web APIs. In October 1994, the World Wide Web Consortium (W3C) was founded to provide oversight and standards for web features. Prior to this point, browsers would often introduce new HTML elements or APIs, and competing browsers would have to copy them. With a standards organization, those elements and APIs could subsequently be agreed upon and documented in specifications. (These days, an initial discussion, design and specification precedes any new feature.) Later on, the HTML specification ended up moving to a different standards body called the WHATWG, but CSS and other features are still standardized at the W3C. JavaScript is standardized at TC39 (“Technical Committee 39” at ECMA, yet another standards body). HTTP is standardized by the IETF. The point is that the standards process set up in the mid-nineties is still with us.

In the first years of the web, it was not so clear that browsers would remain standard and that one browser might not end up “winning” and becoming another proprietary software platform. There are multiple reasons this didn’t happen, among them the egalitarian ethos of the computing community and the presence and strength of the W3C. Another important reason was the networked nature of the web, and therefore the necessity for web developers to make sure their pages worked correctly in most or all of the browsers (otherwise they would lose customers), leading them to avoid proprietary extensions. On the contrary—browsers worked hard to carefully reproduce each other’s undocumented behaviors—even bugs—to make sure they continued supporting the whole web.

There never really was a point where any browser openly attempted to break away from the standard, despite fears that that might happen.Perhaps the closest the web came to fragmenting was with the late-90s introduction of features for DHTML—early versions of the Document Object Model you’ll learn about in this book. Netscape and Internet Explorer at first had incompatible implementations of these features, and it took years, development of a common specification, and significant pressure campaigns on the browsers before standardization was achieved. You can read about this story in much more depth here. Instead, intense competition for market share was channeled into very fast innovation and an ever-expanding set of APIs and capabilities for the web, which we nowadays refer to as the web platform, not just the “World Wide Web”. This recognizes the fact that the web is no longer a document viewing mechanism, but has evolved into a fully realized computing platform and ecosystem.There have even been operating systems built around the web! Examples include webOS, which powered some Palm smartphones, Firefox OS (that today lives on in KaiOS-based phones), and ChromeOS, which is a desktop operating system. All of these OSes are based on using the Web as the UI layer for all applications, with some JavaScript-exposed APIs on top for system integration.

Given the outcomes—multiple competing browsers and well-developed standards—it is in retrospect not that relevant which browser “won” or “lost” each of the browser “wars”. In both cases the web won and was preserved and enhanced for the future.

Open source

Another important and interesting outcome of the second browser war was that all mainstream browsers today (of which there are many more than threeExamples of Chromium-based browsers include Chrome, Edge, Opera (which switched to Chromium from the Presto engine in 2013), Samsung Internet, Yandex Browser, UC Browser and Brave. In addition, there are many “embedded” browsers, based on one or another of the three engines, for a wide variety of automobiles, phones, TVs and other electronic devices.) are based on three open-source web rendering / JavaScript engines: Chromium, Gecko and WebKit.The JavaScript engines are actually in different repositories (as are various other sub-components that we won’t get into here), and can and do get used outside the browser as JavaScript virtual machines. One important application is the use of v8 to power node.js. However, each of the three rendering engines does have a corresponding JavaScript implementation, so conflating the two is reasonable. Since Chromium and WebKit have a common ancestral codebase, while Gecko is an open-source descendant of Netscape, all three date back to the 1990s—almost to the beginning of the web.

This is not an accident, and in fact tells us something quite interesting about the most cost-effective way to implement a rendering engine based on a commodity set of platform APIs. For example, it’s common for a wide variety of independent developers (ones not paid by the company nominally controlling the browser) to contribute code and features. There are even companies and individuals that specialize in implementing these features! And every major browser being open source feeds back into the standards process, reinforcing the web’s decentralized nature.

Putting it all together

In summary, the history went like this:

1. Basic research was performed into the ways to represent and explore information.

2. Once the technology became mature enough, the web proper was proposed and implemented.

3. The web became popular quite quickly, and many browsers appeared in order to capitalize on the web’s opportunity.

4. Standards organizations were introduced in order to negotiate between the browsers and avoid proprietary control.

5. Browsers continued to compete and evolve at a rapid pace; that pace has overall not slowed in the years since.

6. Browsers appeared on all devices and operating systems, including all desktop and mobile devices & OSes, as well as embedded devices such as televisions, watches and kiosks.

7. The web continued to grow in power and complexity, even going beyond the original conception of a web browser.

8. Eventually, all web rendering engines became open source, as a recognition of their being a shared effort larger than any single entity.

The web has come a long way! It’ll be interesting to see where it goes in the future.

But one thing seems clear: it isn’t done yet.

Exercises

What comes next: Based on what you learned about how the web came about and took its current form, what trends do you predict for its future evolution? For example, do you think it’ll compete effectively against other non-web technologies and platforms?

What became of the original ideas? The way the web works in practice is significantly different than the memex; one key difference is that there is no built-in way for the user of the web to add links between pages or notate them. Why do you think this is? Can you think of other goals from the original work that remain unrealized?

A web browser displays information identified by a URL. And the first step is to use that URL to connect to and download that information from a server somewhere on the Internet.

Connecting to a server

Browsing the internet starts with a URL,“URL” stands for “Uniform Resource Locator”, meaning that it is a portable (uniform) way to identify web pages (resources) and also that it describes how to access those files (locator). a short string that identifies a particular web page that the browser should visit. A URL looks like this:

httpScheme://example.orgHostname/index.htmlPath

This URL has three parts: the scheme explains how to get the information; the host explains where to get it; and the path explains what information to get. There are also optional parts to the URL, like ports, queries, and fragments, which we’ll see later.

From a URL, the browser can start the process of downloading the web page. The browser first asks the OS to put it in touch with the server described by the host name. The OS then talks to a DNS server which convertsOn some systems, you can run dig +short example.org to do this conversion yourself. a host name like example.org into a destination IP address like 93.184.216.34.Today there are two versions of IP: IPv4 and IPv6. IPv6 addresses are a lot longer and are usually in hex, but otherwise the differences don’t matter here. Then the OS decides which hardware is best for communicating with that destination IP address (say, wireless or wired) using what is called a routing table, and then uses device drivers to send signals over a wire or over the air.I’m skipping steps here. On wires you first have to wrap communications in ethernet frames, on wireless you have to do even more. I’m trying to be brief. Those signals are picked up and transmitted by a series of routersOr a switch, or an access point, there are a lot of possibilities, but eventually there is a router. which each choose the best direction to send your message so that it eventually gets to the destination.They may also record where the message came from so they can forward the reply back, especially in the case of NATs. When the message reaches the server, a connection is created. Anyway, the point of this is that the browser tells the OS, “Hey, put me in touch with example.org”, and it does.

On many systems, you can set up this kind of connection using the telnet program, like this:The “80” is the port, discussed below.

telnet example.org 80

nc -v example.org 80

You’ll get output that looks like this:

Trying 93.184.216.34...
Connected to example.org.
Escape character is '^]'.

This means that the OS converted the host name example.org into the IP address 93.184.216.34 and was able to connect to it.The line about escape characters is just instructions on using obscure telnet features. You can now talk to example.org.

Requesting information

Once it’s connected, the browser requests information from the server by giving its path, the path being the part of a URL that comes after the host name, like /index.html. The request looks like this; you should type it into telnet:

GETMethod /index.htmlPath HTTP/1.0HTTP Version
HostHeader: example.orgValue

Make sure to type a blank line after the Host line.

Here, the word GET means that the browser would like to receive information,It could say POST if it intended to send information, plus there are some other, more obscure options. then comes the path, and finally there is the word HTTP/1.0 which tells the host that the browser speaks version 1.0 of HTTP.Why not 1.1? You can use 1.1, but then you need another header (Connection) to handle a feature called “keep-alive”. Using 1.0 avoids this complexity. There are several versions of HTTP (0.9, 1.0, 1.1, and 2.0). The HTTP 1.1 standard adds a variety of useful features, like keep-alive, but in the interest of simplicity our browser won’t use them. We’re also not implementing HTTP 2.0; HTTP 2.0 is much more complex than the 1.X series, and is intended for large and complex web applications, which our browser can’t run anyway.

After the first line, each line contains a header, which has a name (like Host) and a value (like example.org). Different headers mean different things; the Host header, for example, tells the server who you think it is.This is useful when the same IP address corresponds to multiple host names and hosts multiple websites (for example, example.com and example.org). The Host header tells the server which of multiple websites you want. These websites basically require the Host header to function properly. Hosting multiple domains on a single computer is very common. There are lots of other headers one could send, but let’s stick to just Host for now.

Finally, after the headers comes a single blank line; that tells the host that you are done with headers. So type a blank line into telnet (hit Enter twice after typing the two lines of request above) and you should get a response from example.org.

The server’s response

The server’s response starts with this line:

HTTP/1.0HTTP Version 200Response Code OKResponse Description

That tells you that the host confirms that it, too, speaks HTTP/1.0, and that it found your request to be “OK” (which has a numeric code of 200). You may be familiar with 404 Not Found; that’s another numeric code and response, as are 403 Forbidden or 500 Server Error. There are lots of these codes,As any look at a flow chart will show. and they have a pretty neat organization scheme:The status text like OK can actually be anything and is just there for humans, not for machines.

• The 100s are informational messages
• The 200s mean you were successful
• The 300s request follow-up action (usually a redirect)
• The 400s mean you sent a bad request
• The 500s mean the server handled the request badly

Note the genius of having two sets of error codes (400s and 500s), which tells you who is at fault, the server or the browser.More precisely, who the server thinks is at fault. You can find a full list of the different codes on Wikipedia, and new ones do get added here and there.

After the 200 OK line, the server sends its own headers. When I did this, I got these headers (but yours will differ):

Age: 545933
Cache-Control: max-age=604800
Content-Type: text/html; charset=UTF-8
Date: Mon, 25 Feb 2019 16:49:28 GMT
Etag: "1541025663+gzip+ident"
Expires: Mon, 04 Mar 2019 16:49:28 GMT
Last-Modified: Fri, 09 Aug 2013 23:54:35 GMT
Server: ECS (sec/96EC)
Vary: Accept-Encoding
X-Cache: HIT
Content-Length: 1270
Connection: close

There is a lot here, about the information you are requesting (Content-Type, Content-Length, and Last-Modified), about the server (Server, X-Cache), about how long the browser should cache this information (Cache-Control, Expires, Etag), about all sorts of other stuff. Let’s move on for now.

After the headers there is a blank line followed by a bunch of HTML code. This is called the body of the server’s response, and your browser knows that it is HTML because of the Content-Type header, which says that it is text/html. It’s this HTML code that contains the content of the web page itself.

Let’s now switch gears from manual connections to Python.

Telnet in Python

So far we’ve communicated with another computer using telnet. But it turns out that telnet is quite a simple program, and we can do the same programmatically. It’ll require extracting host name and path from the URL, creating a socket, sending a request, and receiving a response.In Python, there’s a library called urllib.parse for parsing URLs, but I think implementing our own will be good for learning. Plus, it makes this book less Python-specific.

Let’s start with parsing the URL. I’m going to make parsing a URL return a URL object, and I’ll put the parsing code into the constructor:

class URL:
    def __init__(self, url):
        # ...

The __init__ method is Python’s peculiar syntax for class constructors, and the self parameter, which you must always make the first parameter of any method, is Python’s analog of this.

Let’s start with the scheme, which is separated from the rest of the URL by ://. Our browser only supports http, so I check that, too:

class URL:
    def __init__(self, url):
        self.scheme, url = url.split("://", 1)
        assert self.scheme == "http", \
            "Unknown scheme {}".format(self.scheme)

Now we must separate the host from the path. The host comes before the first /, while the path is that slash and everything after it. Let’s add function that parses all parts of a URL:

class URL:
    def __init__(self, url):
        # ...
        if "/" not in url:
            url = url + "/"
        self.host, url = url.split("/", 1)
        self.path = "/" + url

(When you see a code block with a # ..., like this one, that you’re adding code to an existing method or block.) The split(s, n) method splits a string at the first n copies of s. Note that there’s some tricky logic here for handling the slash between the host name and the path. That (optional) slash is part of the path.

Our browser will create a URL object based on user input, and then it will want to download the web page at that URL. We’ll do that in a new method, request:

class URL:
    def request(self):
        # ...

Note that you always need to write the self parameter for methods in Python. In the future, I won’t always make such a big deal out of defining a method—if you see a code block with code in a method or function that doesn’t exist yet, that means we’re defining it.

The first step to downloading a web page is connecting to the host. The operating system provides a feature called “sockets” for this. When you want to talk to other computers (either to tell them something, or to wait for them to tell you something), you create a socket, and then that socket can be used to send information back and forth. Sockets come in a few different kinds, because there are multiple ways to talk to other computers:

• A socket has an address family, which tells you how to find the other computer. Address families have names that begin with AF. We want AF_INET, but for example AF_BLUETOOTH is another.
• A socket has a type, which describes the sort of conversation that’s going to happen. Types have names that begin with SOCK. We want SOCK_STREAM, which means each computer can send arbitrary amounts of data over, but there’s also SOCK_DGRAM, in which case they send each other packets of some fixed size.The DGRAM stands for “datagram” and think of it like a postcard.
• A socket has a protocol, which describes the steps by which the two computers will establish a connection. Protocols have names that depend on the address family, but we want IPPROTO_TCP.Newer versions of HTTP use something called QUIC instead of TCP, but our browser will stick to HTTP 1.0.

By picking all of these options, we can create a socket like so:While this code uses the Python socket library, your favorite language likely contains a very similar library. This API is basically standardized. In Python, the flags we pass are defaults, so you can actually call socket.socket(); I’m keeping the flags here in case you’re following along in another language.

import socket

class URL:
    def request(self):
        s = socket.socket(
            family=socket.AF_INET,
            type=socket.SOCK_STREAM,
            proto=socket.IPPROTO_TCP,
        )

Once you have a socket, you need to tell it to connect to the other computer. For that, you need the host and a port. The port depends on the type of server you’re connecting to; for now it should be 80.

class URL:
    def request(self):
        # ...
        s.connect((self.host, 80))

This talks to example.org to set up the connection and ready both computers to exchange data.

Note that there are two parentheses in the connect call: connect takes a single argument, and that argument is a pair of a host and a port. This is because different address families have different numbers of arguments.

Request and response

Now that we have a connection, we make a request to the other server. To do so, we send it some data using the send method:

class URL:
    def request(self):
        # ...
        s.send(("GET {} HTTP/1.0\r\n".format(self.path) + \
                "Host: {}\r\n\r\n".format(self.host)) \
               .encode("utf8"))

There are a few things to note here that have to be exactly right. First, it’s very important to use \r\n instead of \n for newlines. It’s also essential that you put two newlines \r\n at the end, so that you send that blank line at the end of the request. If you forget that, the other computer will keep waiting on you to send that newline, and you’ll keep waiting on its response.Computers are endlessly literal-minded.

Also note the encode call. When you send data, it’s important to remember that you are sending raw bits and bytes; they could form text or an image or video. But a Python string is specifically for representing text. The encode method converts text into bytes, and there’s a corresponding decode method that goes the other way.When you call encode and decode you need to tell the computer what character encoding you want it to use. This is a complicated topic. I’m using utf8 here, which is a common character encoding and will work on many pages, but in the real world you would need to be more careful. Python reminds you to be careful by giving different types to text and to bytes:

>>> type("text")
<class 'str'>
>>> type("text".encode("utf8"))
<class 'bytes'>

If you see an error about str versus bytes, it’s because you forgot to call encode or decode somewhere.

Finally, send just sends the request to the server.send actually returns a number, in this case 47. That tells you how many bytes of data you sent to the other computer; if, say, your network connection failed midway through sending the data, you might want to know how much you sent before the connection failed. To read its response, you’d generally use the read function on sockets, which gives whatever bits of the response have already arrived. Then you write a loop that collects bits of the response as they arrive. However, in Python you can use the makefile helper function, which hides the loop:If you’re in another language, you might only have socket.read available. You’ll need to write the loop, checking the socket status, yourself.

class URL:
    def request(self):
        # ...
        response = s.makefile("r", encoding="utf8", newline="\r\n")

Here makefile returns a file-like object containing every byte we receive from the server. I am instructing Python to turn those bytes into a string using the utf8 encoding, or method of associating bytes to letters.Hard-coding utf8 is not correct, but it’s a shortcut that will work alright on most English-language websites. In fact, the Content-Type header usually contains a charset declaration that specifies encoding of the body. If it’s absent, browsers still won’t default to utf8; they’ll guess, based on letter frequencies, and you see ugly � strange áççêñ£ß when they guess wrong. Incorrect-but-common utf8 skips all that complexity. I’m also informing Python of HTTP’s weird line endings.

Let’s now split the response into pieces. The first line is the status line:

class URL:
    def request(self):
        # ...
        statusline = response.readline()
        version, status, explanation = statusline.split(" ", 2)
        assert status == "200", "{}: {}".format(status, explanation)

Note that I do not check that the server’s version of HTTP is the same as mine; this might sound like a good idea, but there are a lot of misconfigured servers out there that respond in HTTP 1.1 even when you talk to them in HTTP 1.0.Luckily the protocols are similar enough to not cause confusion.

After the status line come the headers:

class URL:
    def request(self):
        # ...
        headers = {}
        while True:
            line = response.readline()
            if line == "\r\n": break
            header, value = line.split(":", 1)
            headers[header.lower()] = value.strip()

For the headers, I split each line at the first colon and fill in a map of header names to header values. Headers are case-insensitive, so I normalize them to lower case. Also, white-space is insignificant in HTTP header values, so I strip off extra whitespace at the beginning and end.

Headers can describe all sorts of information, but a couple of headers are especially important because they tell us that the data we’re trying to access is being sent in an unusual way. Let’s make sure none of those are present:The “compression” exercise at the end of this chapter describes how your browser should handle these headers if they are present.

class URL:
    def request(self):
        # ...
        assert "transfer-encoding" not in headers
        assert "content-encoding" not in headers

The usual way to send the data, then, is everything after the headers:

class URL:
    def request(self):
        # ...
        body = response.read()
        s.close()

It’s that body that we’re going to display, so let’s return that. Let’s also return the headers, in case they are useful to someone:

class URL:
    def request(self):
        # ...
        return headers, body

Now let’s actually display the text in the response body.

Displaying the HTML

The HTML code in the body defines the content you see in your browser window when you go to http://example.org/index.html. I’ll be talking much, much more about HTML in future chapters, but for now let me keep it very simple.

In HTML, there are tags and text. Each tag starts with a < and ends with a >; generally speaking, tags tell you what kind of thing some content is, while text is the actual content.That said, some tags, like img, are content, not information about it. Most tags come in pairs of a start and an end tag; for example, the title of the page is enclosed in a pair of tags: <title> and </title>. Each tag, inside the angle brackets, has a tag name (like title here), and then optionally a space followed by attributes, and its pair has a / followed by the tag name (and no attributes). Some tags do not have pairs, because they don’t surround text, they just carry information. For example, on http://example.org/index.html, there is the tag:

<meta charset="utf-8" />

This tag explains that the character set with which to interpret the page body is utf-8. Sometimes, tags that don’t contain information end in a slash, but not always; it’s a matter of preference.

The most important HTML tag is called <body> (with its pair, </body>). Between these tags is the content of the page; outside of these tags is various information about the page, like the aforementioned title, information about how the page should look (<style> and </style>), and metadata (the aforementioned <meta> tag).

So, to create our very, very simple web browser, let’s take the page HTML and print all the text, but not the tags, in it:If this example causes Python to produce a SyntaxError pointing to the end on the last line, it is likely because you are running Python 2 instead of Python 3. These chapters assume Python 3.

in_angle = False
for c in body:
    if c == "<":
        in_angle = True
    elif c == ">":
        in_angle = False
    elif not in_angle:
        print(c, end="")

This code is pretty complex. It goes through the request body character by character, and it has two states: in_angle, when it is currently between a pair of angle brackets, and not in_angle. When the current character is an angle bracket, it changes between those states; normal characters not inside a tag, are printed.The end argument tells Python not to print a newline after the character, which it otherwise would.

Let’s put this code into a new function, show:

def show(body):
    # ...

We can now load a web page just by stringing together request and show:

def load(url):
    headers, body = url.request()
    show(body)

Add the following code to run load from the command line:

if __name__ == "__main__":
    import sys
    load(URL(sys.argv[1]))

This is Python’s version of a main function—it reads the first argument (sys.argv[1]) from the command line and uses it as a URL. Try running this code on the URL http://example.org/:

python3 browser.py http://example.org/

You should see some short text welcoming you to the official example web page. You can also try using it on this chapter!

Encrypted connections

So far, our browser supports the http scheme. That’s pretty good: it’s the most common scheme on the web today. But more and more, websites are migrating to the https scheme. I’d like this toy browser to support https because many websites today require it.

The difference between http and https is that https is more secure—but let’s be a little more specific. The https scheme, or more formally HTTP over TLS, is identical to the normal http scheme, except that all communication between the browser and the host is encrypted. There are quite a few details to how this works: which encryption algorithms are used, how a common encryption key is agreed to, and of course how to make sure that the browser is connecting to the correct host.

Luckily, the Python ssl library implements all of these details for us, so making an encrypted connection is almost as easy as making a regular connection. That ease of use comes with accepting some default settings which could be inappropriate for some situations, but for teaching purposes they are fine.

Making an encrypted connection with ssl is pretty easy. Suppose you’ve already created a socket, s, and connected it to example.org. To encrypt the connection, you use ssl.create_default_context to create a context ctx and use that context to wrap the socket s. That produces a new socket, s:

import ssl
ctx = ssl.create_default_context()
s = ctx.wrap_socket(s, server_hostname=host)

When you wrap s, you pass a server_hostname argument, and it should match the Host header. Note that I save the new socket back into the s variable. That’s because you don’t want to send over the original socket; it would be unencrypted and also confusing.

Let’s try to take this code and add it to request. First, we need to detect which scheme is being used:

class URL:
    def __init__(self, url):
        self.scheme, url = url.split("://", 1)
        assert self.scheme in ["http", "https"], \
            "Unknown scheme {}".format(self.scheme)
        # ...

(Note that here you’re supposed to replace the existing scheme parsing code with this new code. It’s usually clear from context and the code itself what you need to replace.)

Encrypted HTTP connections usually use port 443 instead of port 80:

class URL:
    def __init__(self, url):
        # ...
        if self.scheme == "http":
            self.port = 80
        elif self.scheme == "https":
            self.port = 443

We can use that port when creating the socket:

class URL:
    def request(self):
        # ...
        s.connect((self.host, self.port))
        # ...

Next, we’ll wrap the socket with the ssl library:

class URL:
    def request(self):
        # ...
        if self.scheme == "https":
            ctx = ssl.create_default_context()
            s = ctx.wrap_socket(s, server_hostname=self.host)
        # ...

Your browser should now be able to connect to HTTPS sites.

While we’re at it, let’s add support for custom ports, which are specified in a URL by putting a colon after the host name:

http://example.org:8080Port/index.html

If the URL has a port we can parse it out and use it:

class URL:
    def __init__(self, url):
        # ...
        if ":" in self.host:
            self.host, port = self.host.split(":", 1)
            self.port = int(port)

Custom ports are handy for debugging. Python has a built-in web server you can use to serve files on your computer. For example, if you run

python3 -m http.server 8000

from some directory, then going to http://localhost:8000/ should show you all the files in that directory. This is going to be a good way to test your browser.

Summary

This chapter went from an empty file to a rudimentary web browser that can:

• Parse a URL into a scheme, host, port and path.
• Connect to that host using the sockets and ssl libraries
• Send an HTTP request to that host, including a Host header
• Split the HTTP response into a status line, headers, and a body
• Print the text (and not the tags) in the body

Yes, this is still more of a command-line tool than a web browser, but it already has some of the core capabilities of a browser.

Outline

The complete set of functions, classes, and methods in our browser should look something like this:

Exercises

Alternate encodings: add support for a non-utf8 value for Content-Type. Test it on a real site such as google.com (which doesn’t use utf8).

HTTP/1.1: Along with Host, send the Connection header in the request function with the value close. Your browser can now declare that it is using HTTP/1.1. Also add a User-Agent header. Its value can be whatever you want—it identifies your browser to the host. Make it easy to add further headers in the future.

File URLs: Add support for the file scheme, which allows the browser to open local files. For example, file:///path/goes/here should refer to the file on your computer at location /path/goes/here. Also make it so that, if your browser is started without a URL being given, some specific file on your computer is opened. You can use that file for quick testing.

data: Yet another scheme is data, which allows inlining HTML content into the URL itself. Try navigating to data:text/html,Hello world! in a real browser to see what happens. Add support for this scheme to your browser. The data scheme is especially convenient for making tests without having to put them in separate files.

Body tag: Only show text in an HTML document if it is between <body> and </body>. This avoids printing the title and style information. Try to do this in a single pass through the document—that means not using string methods like split or similar. The loop in show will need more variables to track tag names.

Entities: Implement support for the less-than (<) and greater-than (>) entities. These should be printed as < and >, respectively. For example, if the HTML response was <div>, the show method of your browser should print <div>. Entities allow web pages to include these special characters without the browser interpreting them as tags.

view-source: In addition to HTTP and HTTPS, there are other schemes, such as view-source; navigating in a real browser to view-source:http://browser.engineering/http.html shows the HTML source of this chapter rather than its rendered output. Add support for the view-source scheme. Your browser should print the entire HTML file as if it was text. Hint: To do so, you can utilize the entities from the previous exercise, and add an extra transform() method that adjusts the input to show() when in view-source mode, like this: show(transform(body)).

Compression: Add support for HTTP compression, in which the browser informs the server that compressed data is acceptable. Your browser must send the Accept-Encoding header with the value gzip. If the server supports compression, its response will have a Content-Encoding header with value gzip. The body is then compressed. Add support for this case. To decompress the data, you can use the decompress method in the gzip module. Calling makefile with the encoding argument will no longer work, because compressed data is not utf8-encoded. You can change the first argument "rb" to work with raw bytes instead of encoded text. Most web servers send compressed data in a Transfer-Encoding called chunked. You’ll need to add support for that, too, to access most web servers that support compressed data.There’s also a couple of Transfer-Encodings that compress the data. Those aren’t commonly used.

Redirects: Error codes in the 300 range request a redirect. When your browser encounters one, it should make a new request to the URL given in the Location header. Sometimes the Location header is a full URL, but sometimes it skips the host and scheme and just starts with a / (meaning the same host and scheme as the original request). The new URL might itself be a redirect, so make sure to handle that case. You don’t, however, want to get stuck in a redirect loop, so make sure limit how many redirects your browser can follow in a row. You can test this with the URL http://browser.engineering/redirect, which redirects back to this page.

Caching: Typically the same images, styles, and scripts are used on multiple pages; downloading them repeatedly is a waste. It’s generally valid to cache any HTTP response, as long as it was requested with GET and received a 200 response.Some other status codes like 301 and 404 can also be cached. Implement a cache in your browser and test it by requesting the same file multiple times. Servers control caches using the Cache-Control header. Add support for this header, specifically for no-store and max-age values. If the Cache-Control header contains any other value than these two, it’s best not to cache the response.

A web browser doesn’t just download a web page; it also has to show that page to the user. In the 21^st century, that means a graphical application. How does that work? In this chapter we’ll equip the toy browser with a graphical user interface.There are some obscure text-based browsers: I used w3m as my main browser for most of 2011. I don’t anymore.

Creating windows

Desktop and laptop computers run operating systems that provide desktop environments: windows, buttons, and a mouse. So programs don’t directly draw to the screen; the desktop environment controls the screen. Instead:

• The program asks for a new window and the desktop environment shows it somewhere on the screen.
• The program draws things in its window and the desktop environment puts that on the screen.
• The desktop environment tells the program about clicks and key presses.
• The desktop environment periodically asks the program to redraw its window.

Though the desktop environment is responsible for displaying the window, the program is responsible for drawing its contents. Applications have to redraw these contents quickly for interactions to feel fluid,On older systems, applications drew directly to the screen, and if they didn’t update, whatever was there last would stay in place, which is why in error conditions you’d often have one window leave “trails” on another. Modern systems use a technique called compositing, in part to avoid trails (performance and application isolation are additional reasons). Even while using compositing, applications must redraw their window contents to change what is displayed. Chapter 13 will discuss compositing in more detail. and must respond quickly to clicks and key presses so the user doesn’t get frustrated.

“Feel fluid” can be made more precise. Graphical applications such as browsers typically aim to redraw at a speed equal to the refresh rate, or frame rate, of the screen, and/or a fixed 60HzMost screens today have a refresh rate of 60Hz, and that is generally considered fast enough to look smooth. However, new hardware is increasingly appearing with higher refresh rates, such as 120Hz. Sometimes rendering engines, games in particular, refresh at lower rates on purpose if they know the rendering speed can’t keep up.. This means that the browser has to finish all its work in less than 1/60th of a second, or 16ms, in order to keep up. For this reason, 16ms is called the animation frame budget of the application.

Doing all of this by hand is a bit of a drag, so programs usually use a graphical toolkit to simplify these steps. These toolkits allow you to describe your program’s window in terms of widgets like buttons, tabs, or text boxes, and take care of drawing and redrawing the window contents to match that description.

Python comes with a graphical toolkit called Tk using the Python package tkinter.The library is called Tk, and it was originally written for a different language called Tcl. Python contains an interface to it, hence the name. Using it is quite simple:

import tkinter
window = tkinter.Tk()
tkinter.mainloop()

Here tkinter.Tk() creates a window and tkinter.mainloop() starts the process of redrawing the screen. Inside Tk, tkinter.Tk() asks the desktop environment to create the window and returns its identifier, while tkinter.mainloop() enters a loop that looks similar to this The example event loop above may look like an infinite loop that locks up the computer, but it’s not, because of preemptive multitasking among threads and processes and/or a variant of the event loop that sleeps unless it has inputs that wake it up from another thread or process.:

while True:
    for evt in pendingEvents():
        handleEvent(evt)
    drawScreen()

Here, drawScreen draws the various widgets, pendingEvent asks the desktop environment for recent mouse clicks or key presses, and handleEvent calls into library user code in response to that event. This event loop pattern is common in many applications, from web browsers to video games. A simple window does not need much event handling (it ignores all events) or much drawing (it is a uniform white or gray). But in more complex graphical applications the event loop pattern makes sure that all events are eventually handled and the screen is eventually updated, both essential to a good user experience.

Drawing to the window

Our toy browser will draw the web page text to a canvas, a rectangular Tk widget that you can draw circles, lines, and text in.You may be familiar with the HTML <canvas> element, which is a similar idea: a 2D rectangle in which you can draw shapes. Tk also has widgets like buttons and dialog boxes, but our browser won’t use them: we will need finer-grained control over appearance, which a canvas provides:This is why desktop applications are more uniform than web pages: desktop applications generally use the widgets provided by a common graphical toolkit, which limits their creative possibilities.

WIDTH, HEIGHT = 800, 600
window = tkinter.Tk()
canvas = tkinter.Canvas(window, width=WIDTH, height=HEIGHT)
canvas.pack()

The first line creates the window, as above; the second creates the Canvas inside that window. We pass the window as an argument, so that Tk knows where to display the canvas, and some arguments that define the canvas’s size; I chose 800×600 because that was a common old-timey monitor size.This size, called Super Video Graphics Array, was standardized in 1987, and probably did seem super back then. The third line is a Tk peculiarity, which positions the canvas inside the window.

There’s going to be a window, a canvas, and later some other things, so to keep it all organized let’s make an object:

class Browser:
    def __init__(self):
        self.window = tkinter.Tk()
        self.canvas = tkinter.Canvas(
            self.window, 
            width=WIDTH,
            height=HEIGHT
        )
        self.canvas.pack()

Once you’ve made a canvas, you can call methods that draw shapes on the canvas. Let’s do that inside load, which we’ll move into the new Browser class:

class Browser:
    def load(self, url):
        # ...
        self.canvas.create_rectangle(10, 20, 400, 300)
        self.canvas.create_oval(100, 100, 150, 150)
        self.canvas.create_text(200, 150, text="Hi!")

To run this code, create a Browser, call load, and then start the Tk mainloop:

if __name__ == "__main__":
    import sys
    Browser().load(URL(sys.argv[1]))
    tkinter.mainloop()

You ought to see: a rectangle, starting near the top-left corner of the canvas and ending at its center; then a circle inside that rectangle; and then the text “Hi!” next to the circle.

Coordinates in Tk refer to X positions from left to right and to Y positions from top to bottom. In other words, the bottom of the screen has larger Y values, the opposite of what you might be used to from math. Play with the coordinates above to figure out what each argument refers to.The answers are in the online documentation.

Laying out text

Let’s draw a simple web page on this canvas. So far, the toy browser steps through the web page source code character by character and prints the text (but not the tags) to the console window. Now we want to draw the characters on the canvas instead.

To start, let’s change the show function from the previous chapter into a function that I’ll call lexForeshadowing future developments… which just returns the text-not-tags content of an HTML document, without printing it:

def lex(body):
  text = ""
  # ...
  for c in body:
      # ...
      elif not in_angle:
          text += c
    return text

Then, load will draw that text, character by character:

def load(self, url):
    # ...
    for c in text:
        self.canvas.create_text(100, 100, text=c)

Let’s test this code on a real webpage. For reasons that might seem inscrutableIt’s to delay a discussion of basic typography to the next chapter…, let’s test it on the first chapter of 西游记 or “Journey to the West”, a classic Chinese novel about a monkey. Run this URLRight click on the link and “Copy URL”. through request, lex, and load.If you’re not in Asia, you’ll probably see this phase take a while: China is far away! You should see a window with a big blob of black pixels inset a bit from the top left corner of the window.

Why a blob instead of letters? Well, of course, because we are drawing every letter in the same place, so they all overlap! Let’s fix that:

HSTEP, VSTEP = 13, 18
cursor_x, cursor_y = HSTEP, VSTEP
for c in text:
    self.canvas.create_text(cursor_x, cursor_y, text=c)
    cursor_x += HSTEP

The variables cursor_x and cursor_y point to where the next character will go, as if you were typing the text with in a word processor. I picked the magic numbers—13 and 18—by trying a few different values and picking one that looked most readable. In the next chapter, we’ll replace magic numbers with font metrics.

The text now forms a line from left to right. But with an 800 pixel wide canvas and 13 pixels per character, one line only fits about 60 characters. You need more than that to read a novel, so we also need to wrap the text once we reach the edge of the screen:

for c in text:
    # ...
    if cursor_x >= WIDTH - HSTEP:
        cursor_y += VSTEP
        cursor_x = HSTEP

The code increases cursor_y and resets cursor_xIn the olden days of typewriters, increasing y meant feeding in a new line, and resetting x meant returning the carriage that printed letters to the left edge of the page. So ASCII standardizes two separate characters—“carriage return” and “line feed”—for these operations, so that ASCII could be directly executed by teletypewriters. That’s why headers in HTTP are separated by \r\n, even though modern computers have no mechanical carriage. once cursor_x goes past 787 pixels.Not 800, because we started at pixel 13 and I want to leave an even gap on both sides. Wrapping the text this way makes it possible to read more than a single line:

Now we can read a lot of text, but still not all of it: if there’s enough text, all of the lines of text don’t fit on the screen. We want users to scroll the page to look at different parts of it.

Scrolling text

Scrolling introduces a layer of indirection between page coordinates (this text is 132 pixels from the top of the page) and screen coordinates (since you’ve scrolled 60 pixels down, this text is 72 pixels from the top of the screen). Generally speaking, a browser lays out the page—determines where everything on the page goes—in terms of page coordinates and then renders the page—draws everything—in terms of screen coordinates.Sort of. What actually happens is that the page is first drawn into a bitmap or GPU texture, then that bitmap/texture is shifted according to the scroll, and the result is rendered to the screen. Chapter 12 will have more on this topic.

Our browser will have the same split. Right now load both computes the position of each character and draws it: layout and rendering. Let’s have a layout function to compute and store the position of each character, and a separate draw function to then draw each character based on the stored position. This way, layout can operate with page coordinates and only draw needs to think about screen coordinates.

Let’s start with layout. Instead of calling canvas.create_text on each character let’s add it to a list, together with its position. Since layout doesn’t need to access anything in Browser, it can be a standalone function:

def layout(text):
    display_list = []
    cursor_x, cursor_y = HSTEP, VSTEP
    for c in text:
        display_list.append((cursor_x, cursor_y, c))
        # ...
    return display_list

The resulting list is called a display list: it is a list of things to display.The term is standard. Since layout is all about page coordinates, we don’t need to change anything else about it to support scrolling.

Once the display list is computed, draw needs to loop through the display list and draw each character:

class Browser:
    def draw(self):
        for x, y, c in self.display_list:
            self.canvas.create_text(x, y, text=c)

Since draw does need access to the canvas, we keep it a method on Browser. Now the load just needs to call layout followed by draw:

class Browser:
    def load(self, url):
        headers, body = url.request()
        text = lex(body)
        self.display_list = layout(text)
        self.draw()

Now we can add scrolling. Let’s have a variable for how far you’ve scrolled:

class Browser:
    def __init__(self):
        # ...
        self.scroll = 0

The page coordinate y then has screen coordinate y - self.scroll:

def draw(self):
    for x, y, c in self.display_list:
        self.canvas.create_text(x, y - self.scroll, text=c)

If you change the value of scroll the page will now scroll up and down. But how does the user change scroll?

Reacting to the user

Most browsers scroll the page when you press the up and down keys, rotate the scroll wheel, drag the scroll bar, or apply a touch gesture to the screen. To keep things simple, let’s just implement the down key.

Tk allows you to bind a function to a key, which instructs Tk to call that function when the key is pressed. For example, to bind to the down arrow key, write:

def __init__(self):
    # ...
    self.window.bind("<Down>", self.scrolldown)

Here, self.scrolldown is an event handler, a function that Tk will call whenever the down arrow key is pressed.scrolldown is passed an event object as an argument by Tk, but since scrolling down doesn’t require any information about the key press, besides the fact that it happened, scrolldown ignores that event object. All it needs to do is increment y and re-draw the canvas:

SCROLL_STEP = 100

def scrolldown(self, e):
    self.scroll += SCROLL_STEP
    self.draw()

If you try this out, you’ll find that scrolling draws all the text a second time. That’s because we didn’t erase the old text before drawing the new text. Call canvas.delete to clear the old text:

def draw(self):
    self.canvas.delete("all")
    # ...

Scrolling should now work!

Faster rendering

But this scrolling is pretty slow.How fast exactly seems to depend a lot on your operating system and default font. Why? It turns out that loading information about the shape of a character, inside create_text, takes a while. To speed up scrolling we need to make sure to do it only when necessary (while at the same time ensuring the pixels on the screen are always correct).

Real browsers incorporate a lot of quite tricky optimizations to this process, but for this toy browser let’s limit ourselves to a simple improvement: on a long page most characters are outside the viewing window, and we can skip drawing them in draw:

for x, y, c in self.display_list:
    if y > self.scroll + HEIGHT: continue
    if y + VSTEP < self.scroll: continue
    # ...

The first if statement skips characters below the viewing window; the second skips characters above it. In that second if statement, y + VSTEP computes the bottom edge of the character, so that characters that are halfway inside the viewing window are still drawn.

Scrolling should now be pleasantly fast, and hopefully well within the 16ms animation frame budget. And because we split layout and draw, we don’t need to change layout at all to implement this optimization.

Mobile devices

Though you’re probably writing your browser on a desktop computer, many people access the web through mobile devices such as phones or tablets. On mobile devices, there’s still a screen, a rendering loop, and most other things discussed in this book.For example, most real browsers have both desktop and mobile editions, and the rendering engine code is almost exactly the same for both. But there are several differences worth noting:

• Applications are usually full-screen, with only one application drawing to the screen at a time. Also, “background” applications may be killed and restarted at any time.
• There is always a touch screen, no mouse, and a virtual keyboard instead of a physical one.
• There is a concept of a “visual viewport” not present on desktop. Look at the source of this webpage. In the <head> you’ll see a “viewport” <meta> tag. This tag gives instructions to the browser for how to handle zooming on a mobile device. Without this tag, the browser makes assumptions, for historical reasons, that the site is “desktop-only” and needs some special tricks to make it readable on a mobile device, such as allowing the user to use a pinch-zoom or double-tap touchscreen gesture to focus in on one part of the page. Once zoomed in, the part of the page visible on the screen is the “visual viewport” and the whole documents’ bounds are the “layout viewport”.
• Screen pixel density is much higher, and the total screen resolution is lower.
• Power efficiency is much more important, because the device runs on a battery, while at the same time the CPU and memory are significantly slower and less capable. As a result, it becomes more important to take advantage of GPU hardware on these devices, as well as an even greater focus on performance than usual.

Summary

This chapter went from a rudimentary command-line browser to a graphical user interface with text that can be scrolled. The browser now:

• Talks to your operating system to create a window
• Lays out the text and draws it to that window
• Listens for keyboard commands
• Scrolls the window in response

Next, we’ll make this browser work on English text, with all its complexities of variable width characters, line layout, and formatting.

Outline

The complete set of functions, classes, and methods in our browser should look something like this:

Exercises

Line breaks: Change layout to end the current line and start a new one when it sees a newline character. Increment y by more than VSTEP to give the illusion of paragraph breaks. There are poems embedded in “Journey to the West”; you’ll now be able to make them out.

Mouse wheel: Add support for scrolling up when you hit the up arrow. Make sure you can’t scroll past the top of the page.It’s harder to stop scrolling past the bottom of the page; we will implement this in Chapter 5 Then bind the <MouseWheel> event, which triggers when you scroll with the mouse wheel.It will also trigger with touchpad gestures, if you don’t have a mouse. The associated event object has an event.delta value which tells you how far and in what direction to scroll. Unfortunately, Mac and Windows give the event.delta objects opposite sign and different scales, and on Linux, scrolling instead uses the <Button-4> and <Button-5> events.The Tk manual has more information about this. It’s not easy to write cross-platform applications!

Emoji: Add support for emoji to our browser. Emoji are characters, and you can call create_text to draw them, but the results aren’t very good. Instead, head to the OpenMoji project, download the emoji for “grinning face” as a PNG file, convert to GIF, resize it to 16×16 pixels, and save it to the same folder as the browser. Use Tk’s PhotoImage class to load the image and then the create_image method to draw it to the canvas. In fact, download the whole OpenMoji library (look for the “Get OpenMojis” button at the top right)—then your browser can look up whatever emoji is used in the page.

Resizing: Make the browser resizable. To do so, pass the fill and expand arguments to canvas.pack, call and bind to the <Configure> event, which happens when the window is resized. The window’s new width and height can be found in the width and height fields on the event object. Remember that when the window is resized, the line breaks must change, so you will need to call layout again.

Zoom: Make the + key double the text size. You will need to use the font argument in create_text to change the size of text, like this:

font = tkinter.font.Font(size=32)
canvas.create_text(200, 150, text="Hi!", font=font)

Be careful in how you split the task between layout and draw. Make sure that text doesn’t overlap when you zoom in and that scrolling works when zoomed in.

In the last chapter, your web browser created a graphical window and drew a grid of characters to it. That’s OK for Chinese, but English text features characters of different widths and words that you can’t break across lines.There are lots of languages in the world, and lots of typographic conventions. A real web browser supports every language from Arabic to Zulu, but this book focuses on English. Text is near-infinitely complex, but this book cannot be infinitely long! In this chapter, we’ll add those capabilities. You’ll be able to read this page in your browser!

What is a font?

So far, we’ve called create_text with a character and two coordinates to write text to the screen. But we never specified the font, the size, or the color. To talk about those things, we need to create and use font objects.

What is a font, exactly? Well, in the olden days, printers arranged little metal slugs on rails, covered them with ink, and pressed them to a sheet of paper, creating a printed page. The metal shapes came in boxes, one per letter, so you’d have a (large) box of e’s, a (small) box of x’s, and so on. The boxes came in cases (one for uppercase and one for lowercase letters). The set of cases was called a font.The word is related to foundry, which would create the little metal shapes. Naturally, if you wanted to print larger text, you needed different (bigger) shapes, so those were a different font; a collection of fonts was called a type, which is why we call it typing. Variations—like bold or italic letters—were called that type’s “faces”.

This nomenclature reflects the world of the printing press: metal shapes in boxes in cases of different types. Our modern world instead has dropdown menus, and the old words no longer match it. “Font” can now mean font, typeface, or type,Let alone “font family”, which can refer to larger or smaller collections of types. and we say a font contains several different weights (like “bold” and “normal”),But sometimes other weights as well, like “light”, “semibold”, “black”, and “condensed”. Good fonts tend to come in many weights. several different styles (like “italic” and “roman”, which is what not-italic is called),Sometimes there are other options as well, like maybe there’s a small-caps version; these are sometimes called options as well. And don’t get me started on automatic versus manual italics. and arbitrary sizes.Font looks especially good at certain sizes where hints tell the computer how to best to align it to the pixel grid. Welcome to the world of magic ink.

Yet Tk’s font objects correspond to the older meaning of font: a type at a fixed size, style, and weight. For example:You can only create Font objects, or any other kinds of Tk objects, after calling tkinter.Tk(), which is why I’m putting this code in the Browser constructor.

import tkinter.font

class Browser:
    def __init__(self):
        # ...
        bi_times = tkinter.font.Font(
            family="Times",
            size=16,
            weight="bold",
            slant="italic",
        )

Font objects can be passed to create_text’s font argument:

canvas.create_text(200, 100, text="Hi!", font=bi_times)

Measuring text

Text takes up space vertically and horizontally, and the font object’s metrics and measure methods measure that space:On your computer, you might get different numbers. That’s right—text rendering is OS-dependent, because it is complex enough that everyone uses one of a few libraries to do it, usually libraries that ship with the OS. That’s why macOS fonts tend to be “blurrier” than the same font on Windows: different libraries make different trade-offs.

>>> bi_times.metrics()
{'ascent': 15, 'descent': 7, 'linespace': 22, 'fixed': 0}
>>> bi_times.measure("Hi!")
31

The metrics call yields information about the vertical dimensions of the text: the linespace is how tall the text is, which includes an ascent which goes “above the line” and a descent that goes “below the line”.The fixed parameter is actually a boolean and tells you whether all letters are the same width, so it doesn’t really fit here. The ascent and descent matter when words in different sizes sit on the same line: they ought to line up “along the line”, not along their tops or bottoms.

Let’s dig deeper. Remember that bi_times is size-16 Times: why does font.metrics report that it is actually 22 pixels tall? Well, first of all, size-16 meant sixteen points, which are defined as 72^nds of an inch, not sixteen pixels, which your monitor probably has around 100 of per inch.Tk doesn’t use points anywhere else in its API. It’s supposed to use pixels if you pass it a negative number, but that doesn’t appear to work. Those sixteen points measure not the individual letters but the metal blocks the letters were once carved from, which by necessity were larger than the letters themselves. In fact, different size-16 fonts have letters of varying heights:

>>> tkinter.font.Font(family="Courier", size=16).metrics()
{'fixed': 1, 'ascent': 13, 'descent': 4, 'linespace': 17}
>>> tkinter.font.Font(family="Times", size=16).metrics()
{'fixed': 0, 'ascent': 14, 'descent': 4, 'linespace': 18}
>>> tkinter.font.Font(family="Helvetica", size=16).metrics()
{'fixed': 0, 'ascent': 15, 'descent': 4, 'linespace': 19}

The measure() method is more direct: it tells you how much horizontal space text takes up, in pixels. This depends on the text, of course, since different letters have different width:The sum at the end of this snippet may not work on your machine: the width of a word is not always the sum of the widths of its letters. That’s because Tk uses fractional pixels internally, but rounds up to return whole pixels. For example, some fonts use something called kerning to shift letters a little bit when particular pairs of letters are next to one another.

>>> bi_times.measure("Hi!")
31
>>> bi_times.measure("H")
17
>>> bi_times.measure("i")
6
>>> bi_times.measure("!")
8
>>> 17 + 8 + 6
31

You can use this information to lay text out on the page. For example, suppose you want to draw the text “Hello, world!” in two pieces, so that “world!” is italic. Let’s use two fonts:

font1 = tkinter.font.Font(family="Times", size=16)
font2 = tkinter.font.Font(family="Times", size=16, slant='italic')

We can now lay out the text, starting at (200, 200):

x, y = 200, 200
canvas.create_text(x, y, text="Hello, ", font=font1)
x += font1.measure("Hello, ")
canvas.create_text(x, y, text="world!", font=font2)

You should see “Hello,” and “world!”, correctly aligned and with the second word italicized.

Unfortunately, this code has a bug, though one masked by the choice of example text: replace “world!” with “overlapping!” and the two words will overlap. That’s because the coordinates x and y that you pass to create_text tell Tk where to put the center of the text. It only worked for “Hello, world!” because “Hello,” and “world!” are the same length!

Luckily, the meaning of the coordinate you pass in is configurable. We can instruct Tk to treat the coordinate we gave as the top-left corner of the text by setting the anchor argument to "nw", meaning the “northwest” corner of the text:

x, y = 200, 225
canvas.create_text(x, y, text="Hello, ", font=font1, anchor='nw')
x += font1.measure("Hello, ")
canvas.create_text(x, y, text="overlapping!", font=font2, anchor='nw')

Modify the draw function to set anchor to "nw"; we didn’t need to do that in the previous chapter because all Chinese characters are the same width.

Word by word

In the last chapter, the layout function looped over the text character-by-character and moved to the next line whenever we ran out of space. That’s appropriate in Chinese, where each character more or less is a word. But in English you can’t move to the next line in the middle of a word. Instead, we need to lay out the text one word at a time:This code splits words on whitespace. It’ll thus break on Chinese, since there won’t be whitespace between words. Real browsers use language-dependent rules for laying out text, including for identifying word boundaries.

w = font.measure(word)
if cursor_x + w > WIDTH - HSTEP:
    cursor_y += font.metrics("linespace") * 1.25
    cursor_x = HSTEP
self.display_list.append((cursor_x, cursor_y, word))
cursor_x += w + font.measure(" ")

There’s a lot of moving parts to this code. First, we measure the width of the text, and store it in w. We’d normally draw the text at cursor_x, so its right end would be at cursor_x + w, so we check if that’s past the edge of the page. Now we have the location to start drawing the word, so we add to the display list; and finally we update cursor_x to point to the end of the word.

There are a few surprises in this code. One is that I call metrics with an argument; that just returns the named metric directly. Also, I increment cursor_x by w + font.measure(" ") instead of w. That’s because I want to have spaces between the words: the call to split() removed all of the whitespace, and this adds it back. I don’t add the space to w on the second line, though, because you don’t need a space after the last word on a line.

Finally, note that I multiply the linespace by 1.25 when incrementing y. Try removing the multiplier: you’ll see that the text is harder to read because the lines are too close together.Designers say the text is too “tight”. Instead, it is common to add “line spacing” or “leading”So named because in metal type days, thin pieces of lead were placed between the lines to space them out. Lead is a softer metal than what the actual letter pieces were made of, so it could compress a little to keep pressure on the other pieces. Pronounce it “led-ing” not “leed-ing”. between lines. The 25% line spacing is a normal amount.

Styling text

Right now, all of the text on the page is drawn with one font. But web pages sometimes bold or italicize text using the <b> and <i> tags. It’d be nice to support that, but right now, the code resists the change: the layout function only receives the text of the page as input, and so has no idea where the bold and italics tags are.

Let’s change lex to return a list of tokens, where a token is either a Text object (for a run of characters outside a tag) or a Tag object (for the contents of a tag). You’ll need to write the Text and Tag classes:If you’re familiar with Python, you might want to use the dataclass library, which makes it easier to define these sorts of utility classes.

class Text:
    def __init__(self, text):
        self.text = text

class Tag:
    def __init__(self, tag):
        self.tag = tag

lex must now gather text into Text and Tag objects:If you’ve done exercises in prior chapters, your code will look different. Code snippets in the book always assume you haven’t done the exercises, so you’ll need to port your modifications.

def lex(body):
    out = []
    text = ""
    in_tag = False
    for c in body:
        if c == "<":
            in_tag = True
            if text: out.append(Text(text))
            text = ""
        elif c == ">":
            in_tag = False
            out.append(Tag(text))
            text = ""
        else:
            text += c
    if not in_tag and text:
        out.append(Text(text))
    return out

At the end of the loop, lex dumps any accumulated text as a Text object. Otherwise, if you never saw an angle bracket, you’d return an empty list of tokens. But unfinished tags, like in Hi!<hr, are thrown out.This may strike you as an odd decision: why not raise an error, or finish up the tag for the author? Good questions, but dropping the tag is what browsers do.

Note that Text and Tag are asymmetric: lex avoids empty Text objects, but not empty Tag objects. That’s because an empty Tag object represents the HTML code <>, while an empty Text object with empty text represents no content at all.

Since we’ve modified lex we are now passing layout not just the text of the page, but also the tags in it. So layout must loop over tokens, not text:

def layout(tokens):
    # ...
    for tok in tokens:
        if isinstance(tok, Text):
            for word in tok.text.split():
                # ...
    # ...

layout can also examine tag tokens to change font when directed by the page. Let’s start with support for weights and styles, with two corresponding variables:

weight = "normal"
style = "roman"

Those variables must change when the bold and italics open and close tags are seen:

if isinstance(tok, Text):
    # ...
elif tok.tag == "i":
    style = "italic"
elif tok.tag == "/i":
    style = "roman"
elif tok.tag == "b":
    weight = "bold"
elif tok.tag == "/b":
    weight = "normal"

Note that this code correctly handles not only <b>bold</b> and <i>italic</i> text, but also <b><i>bold italic</i></b> text.It even handles mis-nested tags like <b>b<i>bi</b>i</i>, but it does not handle <b><b>twice</b>bolded</b> text. We’ll return to both in the next chapter.

The bold and italic variables are used to select the font. Since the font is computed in layout but used in draw, we’ll need to add the font used to each entry in the display list.

if isinstance(tok, Text):
    for word in tok.text.split():
        font = tkinter.font.Font(
            size=16,
            weight=weight,
            slant=style,
        )
        # ...
        display_list.append((cursor_x, cursor_y, word, font))

Make sure to update draw to expect and use this extra font field in display list entries.

A layout object

With all of these tags, layout has become quite large, with lots of local variables and some complicated control flow. That is one sign that something deserves to be a class, not a function:

class Layout:
    def __init__(self, tokens):
        self.display_list = []

Every local variable in layout then becomes a field of Layout:

self.cursor_x = HSTEP
self.cursor_y = VSTEP
self.weight = "normal"
self.style = "roman"
self.size = 16

The core of the old layout is a loop over tokens, and we can move the body of that loop to a method on Layout:

def __init__(self, tokens):
    # ...
    for tok in tokens:
        self.token(tok)

def token(self, tok):
    if isinstance(tok, Text):
        for word in tok.text.split():
            # ...
    elif tok.tag == "i":
        self.style = "italic"
    # ...

In fact, the body of the isinstance(tok, Text) branch can be moved to its own method:

def word(self, word):
    font = tkinter.font.Font(
        size=16,
        weight=self.weight,
        slant=self.style,
    )
    w = font.measure(word)
    # ...

Now that everything has moved out of Browser’s old layout function, it can be replaced with calls into Layout:

class Browser:
    def load(self, url):
        headers, body = url.request()
        tokens = lex(body)
        self.display_list = Layout(tokens).display_list
        self.draw()

When you do big refactors like this, it’s important to work incrementally. It might seem more efficient to change everything at once, that efficiency brings with it a risk of failure: trying to do so much that you get confused and have to abandon the whole refactor.

Anyway, this refactor isolated all of the text-handling code into its own method, with the main token function just branching on the tag name. Let’s take advantage of the new, cleaner organization to add more tags. With font weights and styles working, size is the next frontier in typographic sophistication. One simple way to change font size is the <small> tag and its deprecated sister tag <big>.In your web design projects, use the CSS font-size property to change text size instead of <big> and <small>. But since we haven’t implemented CSS for our browser, we’re stuck using them here.

Our experience with font styles and weights suggests a simple approach. First, a field in Layout to track font size:

self.size = 16

That variable is used to create the font object:

font = tkinter.font.Font(
    size=self.size,
    weight=self.weight,
    slant=self.style,
)

Finally, the <big> and <small> tags change the value of size:

def token(self, tok):
    # ...
    elif tok.tag == "small":
        self.size -= 2
    elif tok.tag == "/small":
        self.size += 2
    elif tok.tag == "big":
        self.size += 4
    elif tok.tag == "/big":
        self.size -= 4

Try wrapping a whole paragraph in <small>, like you would a bit of fine print, and enjoy your newfound typographical freedom.

Text of different sizes

Start mixing font sizes, like <small>a</small><big>A</big>, and you’ll quickly notice a problem with the font size code: the text is aligned along its top, not “along the line”, as if it’s hanging from a clothes line.

Let’s think through how to fix this. If the big text is moved up, it would overlap with the previous line, so the smaller text has to be moved down. That means its vertical position has to be computed later, after the big text passes through token. But since the small text comes through the loop first, we need a two-pass algorithm for lines of text: the first pass identifies what words go in the line and computes their x positions, while the second pass vertically aligns the words and computes their y positions.

Let’s start with phase one. Since one line contains text from many tags, we need a field on Layout to store the line-to-be. That field, line, will be a list, and text will add words to it instead of the display list. Entries in line will have x but not y positions, since y positions aren’t computed in the first phase:

class Layout:
    def __init__(self, tokens):
        # ...
        self.line = []
        # ...
    
    def word(self, word):
        # ...
        self.line.append((self.cursor_x, word, font))

The new line field is essentially a buffer, where words are held temporarily before they can be placed. The second phase is that buffer being flushed when we’re finished with a line:

class Layout:
    def word(self, word):
        if self.cursor_x + w > WIDTH - HSTEP:
            self.flush()

As usual with buffers, we also need to make sure the buffer is flushed once all tokens are processed:

class Layout:
    def __init__(self, tokens):
        # ...
        self.flush()

This new flush function has three responsibilities:

1. It must align the words along the line;
2. It must add all those words to the display list; and
3. It must update the cursor_x and cursor_y fields

Here’s what it looks like, step by step:

Since we want words to line up “on the line”, let’s start by computing where that line should be. That depends on the metrics for all the fonts involved:

def flush(self):
    if not self.line: return
    metrics = [font.metrics() for x, word, font in self.line]

We need to locate the tallest word:

max_ascent = max([metric["ascent"] for metric in metrics])

The line is then max_ascent below self.y—or actually a little more to account for the leading:Actually, 25% leading doesn’t add 25% of the ascender above the ascender and 25% of the descender below the descender. Instead, it adds 12.5% of the line height in both places, which is subtly different when fonts are mixed. But let’s skip that subtlety here.

baseline = self.cursor_y + 1.25 * max_ascent

Now that we know where the line is, we can place each word relative to that line and add it to the display list:

for x, word, font in self.line:
    y = baseline - font.metrics("ascent")
    self.display_list.append((x, y, word, font))

Note how y starts at the baseline, and moves up by just enough to accomodate that word’s ascender.

Finally, flush must update the Layout’s x, y, and line fields. x and line are easy:

self.cursor_x = HSTEP
self.line = []

Meanwhile, y must be far enough below baseline to account for the deepest descender:

max_descent = max([metric["descent"] for metric in metrics])
self.cursor_y = baseline + 1.25 * max_descent

Now all the text is aligned along the line, even when text sizes are mixed. Plus, this new flush function is convenient for other line breaking jobs. For example, in HTML the <br> tagWhich is a self-closing tag, so there’s no </br>. Many tags that are content, instead of annotating it, are like this. Some people like adding a final slash to self-closing tags, like <br/>, but this is not required in HTML. ends the current line and starts a new one:

def token(self, tok):
    # ...
    elif tok.tag == "br":
        self.flush()

Likewise, paragraphs are defined by the <p> and </p> tags, so </p> also ends the current line:

def token(self, tok):
    # ...
    elif tok.tag == "/p":
        self.flush()
        self.cursor_y += VSTEP

I add a bit extra to cursor_y here to create a little gap between paragraphs.

Faster text layout

Now that you’ve implemented styled text, you’ve probably noticed—unless you’re on macOSWhile we can’t confirm this in the documentation, it seems that the macOS “Core Text” APIs cache fonts more aggressively than Linux and Windows. The optimization described in this section won’t hurt any on macOS, but also won’t improve speed as much as on Windows and Linux.—that on a large web page like this chapter your browser has slowed significantly from the last chapter. That’s because text layout, and specifically the part where you measure each word, is quite slow.You can profile Python programs by replacing your python3 command with python3 -m cProfile. Look for the lines corresponding to the measure and metrics calls to see how much time is spent measuring text.

Unfortunately, it’s hard to make text measurement much faster. With proportional fonts and complex font features like hinting and kerning, measuring text can require pretty complex computations. But on a large web page, some words likely appear a lot—for example, this page includes the word “the” over two hundred times. Instead of measuring these words over and over again, we could measure them once, and then cache the results. On normal English text, this usually results in a substantial speedup.

Caching is such a good idea that most text libraries already implement it. But because our text method creates a new Font object for each word, our browser isn’t taking advantage of that caching. If we only made a new Font object when we had to, the built-in caches would work better and our browser would be faster. So we’ll need our own cache, so that we can reuse Font objects and have our text measurements cached.

We’ll store our cache in a global FONTS dictionary:

FONTS = {}

The keys to this dictionary will be size/weight/style triples, and the values will be Font objects. We can put the caching logic itself in a new get_font function:

def get_font(size, weight, slant):
    key = (size, weight, slant)
    if key not in FONTS:
        font = tkinter.font.Font(size=size, weight=weight, slant=slant)
        FONTS[key] = font
    return FONTS[key]

Now, inside the text method we can call get_font instead of creating a Font object directly:

class Layout:
    def word(self, word):
        font = get_font(self.size, self.weight, self.style)
        # ...

Summary

The last chapter introduced a browser that laid out Chinese text. Now it does English, too:

• Text is laid out word-by-word
• Lines are split at word boundaries
• Text can be bold or italic
• Text of different sizes can be mixed

You can now use your browser to read an essay, a blog post, or a book!

Outline

The complete set of functions, classes, and methods in our browser should look something like this:

Exercises

Centered Text: This book’s page titles are centered: find them between <h1 class="title"> and </h1>. Make your browser center the text in these titles. Each line has to be centered individually, because different lines will have different lengths.

Superscripts: Add support for the <sup> tag: text in this tag should be smaller (perhaps half the normal text size) and be placed so that the top of a superscript lines up with the top of a normal letter.

Soft hyphens: The soft hyphen character, written \N{soft hyphen} in Python, represents a place where the text renderer can, but doesn’t have to, insert a hyphen and break the word across lines. Add support for it.If you’ve done a previous exercise on HTML entities, you might also want to add support for the ­ entity, which expands to a soft hyphen. If a word doesn’t fit at the end of a line, check if it has soft hyphens, and if so break the word across lines. Remember that a word can have multiple soft hyphens in it, and make sure to draw a hyphen when you break a word. The word “super­cala­fraga­listic­expi­ala­do­shus” is a good test case.

Small caps: Make the <abbr> element render text in small caps, like this. Inside an <abbr> tag, lower-case letters should be small, capitalized, and bold, while all other characters (upper case, numbers, etc) should be drawn in the normal font.

Preformatted text: Add support for the <pre> tag. Unlike normal paragraphs, text inside <pre> tags doesn’t automatically break lines, and whitespace like spaces and newlines are preserved. Use a fixed-width font like Courier New or SFMono as well. Make sure tags work normally inside <pre> tags: it should be possible to bold some text inside a <pre>.

So far, your web browser sees web pages as a stream of open tags, close tags, and text. But HTML is actually a tree, and though the tree structure hasn’t been important yet, it will be once backgrounds, margins, and CSS enter the picture. So this chapter adds a proper HTML parser and converts the layout engine to use it.

A tree of nodes

The HTML treeThis is the tree that is usually called the DOM tree, for Document Object Model. We’ll keep calling it the HTML tree for now. has one node for each open and close tag pair and for each span of text.In reality there are other types of nodes too, like comments, doctypes, and CDATA sections, and processing instructions. There are even some deprecated types! So for our browser to be a tree, tokens need to evolve into nodes. That means adding a list of children and a parent pointer to each one. Here’s the new Text class:The children field of a Text node will always be empty; I’m defining it here to make it easier to write code that handles Text and Element nodes simultaneously.

class Text:
    def __init__(self, text, parent):
        self.text = text
        self.children = []
        self.parent = parent

Since it takes two tags (the open and the close tag) to make a node, let’s rename the Tag class to Element, and make it look like this:

class Element:
    def __init__(self, tag, parent):
        self.tag = tag
        self.children = []
        self.parent = parent

I added a children field to both Text and Element, even though text nodes never have children. That’s for consistency, to avoid isinstance calls throughout the code.

Constructing a tree of nodes from source code is called parsing. A parser builds a tree one element or text node at a time. But that means the parser needs to store an incomplete tree. For example, suppose the parser has so far read this bit of HTML:

<html><head></head><body><h1>This is my webpage

The parser has seen five tags (and one text node). The rest of the HTML will contain more open tags, close tags, and text; but no matter which tokens it sees, no new nodes will be added to the <head> tag, which has already been closed. So that node is “finished”. But the other nodes are unfinished: more children can be added to the <html>, <body>, and <h1> nodes, depending on what HTML comes next.

Since the parser reads the HTML file from left to right, these unfinished tags are always in a certain part of the tree. The unfinished tags have always been opened but not yet closed; they are always to the right of the finished nodes; and they are always children of other unfinished tags. To leverage these facts, let’s represent an incomplete tree by storing a list of unfinished tags, ordered with parents before children. The first node in the list is the root of the HTML tree; the last node in the list is the most recent unfinished tag.In Python, and most other languages, it’s faster to add and remove from the end of a list, instead of the beginning.

Parsing is a little more complex than lex, so we’re going to want to break it into several functions, organized in a new HTMLParser class. That class can also store the source code it’s analyzing and the incomplete tree:

class HTMLParser:
    def __init__(self, body):
        self.body = body
        self.unfinished = []

Before the parser starts, it hasn’t seen any tags at all, so the unfinished list storing the tree starts empty. But as the parser reads tokens, that list fills up. Let’s start that by renaming the lex function we have now, aspirationally, to parse:

class HTMLParser:
    def parse(self):
        # ...

We’ll need to do a bit of surgery on parse. Right now parse creates Tag and Text objects and appends them to the out array. We need it to create Element and Text objects and add them to the unfinished tree. Since a tree is a bit more complex than a list, I’ll move the adding-to-a-tree logic to two new methods add_text and add_tag.

def parse(self):
    text = ""
    in_tag = False
    for c in self.body:
        if c == "<":
            in_tag = True
            if text: self.add_text(text)
            text = ""
        elif c == ">":
            in_tag = False
            self.add_tag(text)
            text = ""
        else:
            text += c
    if not in_tag and text:
        self.add_text(text)
    return self.finish()

The out variable is gone, and note that I’ve also moved the return value to a new finish method, which converts the incomplete tree to the final, complete tree. So: how do we add things to the tree?

Constructing the tree

Let’s talk about adding nodes to a tree. To add a text node we add it as a child of the last unfinished node:

class HTMLParser:
    def add_text(self, text):
        parent = self.unfinished[-1]
        node = Text(text, parent)
        parent.children.append(node)

On the other hand, tags are a little more complex since they might be an open or a close tag:

class HTMLParser:
    def add_tag(self, tag):
        if tag.startswith("/"):
            # ...
        else:
            # ...

A close tag removes an unfinished node, by finishing it, and add it to the next unfinished node in the list:

def add_tag(self, tag):
    if tag.startswith("/"):
        node = self.unfinished.pop()
        parent = self.unfinished[-1]
        parent.children.append(node)
    # ...

An open tag instead adds an unfinished node to the end of the list:

def add_tag(self, tag):
    # ...
    else:
        parent = self.unfinished[-1]
        node = Element(tag, parent)
        self.unfinished.append(node)

Once the parser is done, it turns our incomplete tree into a complete tree by just finishing any unfinished nodes:

class HTMLParser:
    def finish(self):
        if len(self.unfinished) == 0:
            self.add_tag("html")
        while len(self.unfinished) > 1:
            node = self.unfinished.pop()
            parent = self.unfinished[-1]
            parent.children.append(node)
        return self.unfinished.pop()

This is almost a complete parser, but it doesn’t quite work at the beginning and end of the document. The very first open tag is an edge case without a parent:

def add_tag(self, tag):
    # ...
    else:
        parent = self.unfinished[-1] if self.unfinished else None
        # ...

The very last tag is also an edge case, because there’s no unfinished node to add it to:

def add_tag(self, tag):
    if tag.startswith("/"):
        if len(self.unfinished) == 1: return
        # ...

Ok, that’s all done. Let’s test our parser out and see how well it works!

Debugging a parser

How do we know our parser does the right thing—that it builds the right tree? Well the place to start is seeing the tree it produces. We can do that with a quick, recursive pretty-printer:

def print_tree(node, indent=0):
    print(" " * indent, node)
    for child in node.children:
        print_tree(child, indent + 2)

Here we’re printing each node in the tree, and using indentation to show the tree structure. Since we need to print each node, it’s worth taking the time to give them a nice printed form, which in Python means defining the __repr__ function:

class Text:
    def __repr__(self):
        return repr(self.text)

class Element:
    def __repr__(self):
        return "<" + self.tag + ">"

Try this out on this web page, parsing the HTML source code and then calling print_tree to visualize it:

headers, body = URL(sys.argv[1]).request()
nodes = HTMLParser(body).parse()
print_tree(nodes)

Run it on this web page, and you’ll see something like this:

 <!doctype html>
   '\n'
   <html lang="en-US" xml:lang="en-US">
     '\n'
     <head>
       '\n  '
       <meta charset="utf-8" />
         '\n  '
         <meta name="generator" content="pandoc" />
           '\n  '

Immediately a couple of things stand out. Let’s start at the top, with the <!doctype html> tag.

This special tag, called a doctype, is always the very first thing in an HTML document. But it’s not really an element at all, nor is it supposed to have a close tag. Our toy browser won’t be using the doctype for anything, so it’s best to throw it away:Real browsers use doctypes to switch between standards-compliant and legacy parsing and layout modes.

def add_tag(self, tag):
    if tag.startswith("!"): return
    # ...

This ignores all tags that start with an exclamation mark, which not only throws out doctype declarations but also most comments, which in HTML are written <!-- comment text -->.

Just throwing out doctypes isn’t quite enough though—if you run your parser now, it will crash. That’s because after the doctype comes a newline, which our parser treats as text and tries to insert into the tree. Except there isn’t a tree, since the parser hasn’t seen any open tags. For simplicity, let’s just have our browser skip whitespace-only text nodes to side-step the problem:Real browsers retain whitespace to correctly render make<span></span>up as one word and make<span> </span>up as two. Our browser won’t. Plus, ignoring whitespace simplifies later chapters by avoiding a special-case for whitespace-only text tags.

def add_text(self, text):
    if text.isspace(): return
    # ...

The parsed HTML tree now looks like this:

<html lang="en-US" xml:lang="en-US">
   <head>
     <meta charset="utf-8" />
       <meta name="generator" content="pandoc" />
         <meta name="viewport" content="width=device-width,initial-scale=1.0,user-scalable=yes" />
           <meta name="author" content="Pavel Panchekha &amp; Chris Harrelson" />
             <link rel="stylesheet" href="book.css" />
               <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Vollkorn%7CLora&display=swap" />
                 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Vollkorn:400i%7CLora:400i&display=swap" />
                   <title>

Why’s everything so deeply indented? Why aren’t these open elements ever closed?

Self-closing tags

Elements like <meta> and <link> are what are called self-closing: these tags don’t surround content, so you don’t ever write </meta> or </link>. Our parser needs special support for them. In HTML, there’s a specific list of these self-closing tags (the spec calls them “void” tags):A lot of these tags are obscure. Browsers also support some additional, obsolete self-closing tags not listed here, like keygen.

SELF_CLOSING_TAGS = [
    "area", "base", "br", "col", "embed", "hr", "img", "input",
    "link", "meta", "param", "source", "track", "wbr",
]

Our parser needs to auto-close tags from this list:

def add_tag(self, tag):
    # ...
    elif tag in self.SELF_CLOSING_TAGS:
        parent = self.unfinished[-1]
        node = Element(tag, parent)
        parent.children.append(node)

This code is right, but if you test it out it won’t seem to help. Why not? Our parser is looking for a tag named meta, but it’s finding a tag named “meta name=...”. The self-closing code isn’t triggered because the <meta> tag has attributes.

HTML attributes add information about an element; open tags can have any number of attributes. Attribute values can be quoted, unquoted, or omitted entirely. Let’s focus on basic attribute support, ignoring values that contain whitespace, which are a little complicated.

Since we’re not handling whitespace in values, we can split on whitespace to get the tag name and the attribute-value pairs:

class HTMLParser:
    def get_attributes(self, text):
        parts = text.split()
        tag = parts[0].lower()
        attributes = {}
        for attrpair in parts[1:]:
            # ...
        return tag, attributes

HTML tag names are case-insensitive,This is not the right way to do case insensitive comparisons; the Unicode case folding algorithm should be used if you want to handle languages other than English. But in HTML specifically, tag names only use the ASCII characters so lower-casing them is sufficient. as by the way are attribute values, so I convert them to lower case. Then, inside the loop, I split each attribute-value pair into a name and a value. The easiest case is an unquoted attribute, where an equal sign separates the two:

def get_attributes(self, text):
    # ...
    for attrpair in parts[1:]:
        if "=" in attrpair:
            key, value = attrpair.split("=", 1)
            attributes[key.lower()] = value
    # ...

The value can also be omitted, like in <input disabled>, in which case the attribute value defaults to the empty string:

for attrpair in parts[1:]:
    # ...
    else:
        attributes[attrpair.lower()] = ""

Finally, the value can be quoted, in which case the quotes have to be stripped out:Quoted attributes allow whitespace between the quotes. That requires something like a finite state machine instead of just splitting on whitespace.

if "=" in attrpair:
    # ...
    if len(value) > 2 and value[0] in ["'", "\""]:
        value = value[1:-1]
    # ...

We’ll store these attributes inside Elements:

class Element:
    def __init__(self, tag, attributes, parent):
        self.tag = tag
        self.attributes = attributes
        # ...

That means we’ll need to call get_attributes at the top of add_tag, to get the attributes we need to construct an Element.

def add_tag(self, tag):
    tag, attributes = self.get_attributes(tag)

Remember to use tag and attribute instead of text in add_tag, and try your parser again:

<html>
   <head>
     <meta>
     <meta>
     <meta>
     <meta>
     <link>
     <link>
     <link>
     <title>

It’s close! Yes, if you print the attributes, you’ll see that attributes with whitespace (like author on the fourth meta tag) are mis-parsed as multiple attributes, and the final slash on the self-closing tags is incorrectly treated as an extra attribute. A better parser would fix these issues. But let’s instead leave our parser as is—these issues aren’t going to be a problem for the toy browser we’re building—and move on to integrating it with our browser.

Using the node tree

Right now, the Layout class works token-by-token; we now want it to go node-by-node instead. So let’s separate the old token method into three parts: all the cases for open tags will go into a new open_tag method; all the cases for close tags will go into a new close_tag method; and instead of having a case for text tokens our browser can just call the existing text method directly:

class Layout:
    def open_tag(self, tag):
        if tag == "i":
            self.style = "italic"
        # ...

    def close_tag(self, tag):
        if tag == "i":
            self.style = "roman"
        # ...

Now we need the Layout object to walk the node tree, calling open_tag, close_tag, and text in the right order:

def recurse(self, tree):
    if isinstance(tree, Text):
        for word in tree.text.split():
            self.word(word)
    else:
        self.open_tag(tree.tag)
        for child in tree.children:
            self.recurse(child)
        self.close_tag(tree.tag)

The Layout constructor can now call recurse instead of looping through the list of tokens. We’ll also need the browser to construct the node tree, like this:

class Browser:
    def load(self, url):
        headers, body = url.request()
        self.nodes = HTMLParser(body).parse()
        self.display_list = Layout(self.nodes).display_list
        self.draw()

Run it—the browser should now work off of the parsed HTML tree.

Handling author errors

The parser now handles HTML pages correctly—at least when the HTML is written by the sorts of goody-two-shoes programmers who remember the <head> tag, close every open tag, and make their bed in the morning. Mere mortals lack such discipline and so browsers also have to handle broken, confusing, headless HTML. In fact, modern HTML parsers are capable of transforming any string of characters into an HTML tree, no matter how confusing the markup.Yes, it’s crazy, and for a few years in the early ’00s the W3C tried to do away with it. They failed.

The full algorithm is, as you might expect, complicated beyond belief, with dozens of ever-more-special cases forming a taxonomy of human error, but one of its nicer features is implicit tags. Normally, an HTML document starts with a familiar boilerplate:

<!doctype html>
<html>
  <head>
  </head>
  <body>
  </body>
</html>

In reality, all six of these tags, except the doctype, are optional: browsers insert them automatically. Let’s add support for implicit tags to our browser via a new implicit_tags function that adds implicit tags when the web page omits them. We’ll want to call it in both add_text and add_tag:

class HTMLParser:
    def add_text(self, text):
        if text.isspace(): return
        self.implicit_tags(None)
        # ...

    def add_tag(self, tag):
        tag, attributes = self.get_attributes(tag)
        if tag.startswith("!"): return
        self.implicit_tags(tag)
        # ...

Note that implicit_tags isn’t called for the ignored whitespace and doctypes. The argument to implicit_tags is the tag name (or None for text nodes), which we’ll compare to the list of unfinished tags to determine what’s been omitted:

class HTMLParser:
    def implicit_tags(self, tag):
        while True:
            open_tags = [node.tag for node in self.unfinished]
            # ...

implicit_tags has a loop because more than one tag could have been omitted in a row; every iteration around the loop will add just one. To determine which implicit tag to add, if any, requires examining the open tags and the tag being inserted.

Let’s start with the easiest case, the implicit <html> tag. An implicit <html> tag is necessary if the first tag in the document is something other than <html>:

while True:
    # ...
    if open_tags == [] and tag != "html":
        self.add_tag("html")

Both <head> and <body> can also be omitted, but to figure out which it is we need to look at which tag is being added:

while True:
    # ...
    elif open_tags == ["html"] \
         and tag not in ["head", "body", "/html"]:
        if tag in self.HEAD_TAGS:
            self.add_tag("head")
        else:
            self.add_tag("body")

Here, HEAD_TAGS lists the tags that you’re supposed to put into the <head> element:The <script> tag can go in either the head or the body section, but it goes into the head by default.

class HTMLParser:
    HEAD_TAGS = [
        "base", "basefont", "bgsound", "noscript",
        "link", "meta", "title", "style", "script",
    ]

Note that if both the <html> and <head> tags are omitted, implicit_tags is going to insert both of them by going around the loop twice. In the first iteration open_tags is [], so the code adds an <html> tag; then, in the second iteration, open_tags is ["html"] so it adds a <head> tag.These add_tag methods themselves call implicit_tags, which means you can get into an infinite loop if you forget a case. Remember that every time you add a tag in implicit_tags, that tag itself shouldn’t trigger more implicit tags.

Finally, the </head> tag can also be implicit, if the parser is inside the <head> and sees an element that’s supposed to go in the <body>:

while True:
    # ...
    elif open_tags == ["html", "head"] and \
         tag not in ["/head"] + self.HEAD_TAGS:
        self.add_tag("/head")

Technically, the </body> and </html> tags can also be implicit. But since our finish function already closes any unfinished tags, that doesn’t need any extra code. So all that’s left for implicit_tags tags is to exit out of the loop:

while True:
    # ...
    else:
        break

Of course, there are more rules for handling malformed HTML: formatting tags, nested paragraphs, embedded SVG and MathML, and all sorts of other complexity. Each has complicated rules abounding with edge cases. But let’s end our discussion of handling author errors here.

The rules for malformed HTML may seem arbitrary, and they are: they evolved over years of trying to guess what people “meant” when they wrote that HTML, and are now codified in the HTML parsing standard. Of course, sometimes these rules “guess” wrong—but as so often happens on the web, it’s often more important that every browser does the same thing, rather than each trying to guess what the right thing is.

Summary

This chapter taught our browser that HTML is a tree, not just a flat list of tokens. We added:

• A parser to transform HTML tokens to a tree
• Code to recognize and handle attributes on elements
• Automatic fixes for some malformed HTML documents
• A recursive layout algorithm to lay out an HTML tree

The tree structure of HTML is essential to display visually complex web pages, as we will see in the next chapter.

Outline

The complete set of functions, classes, and methods in our browser should look something like this:

Exercises

Comments: Update the HTML lexer to support comments. Comments in HTML begin with <!-- and end with -->. However, comments aren’t the same as tags: they can contain any text, including left and right angle brackets. The lexer should skip comments, not generating any token at all. Check: is <!--> a comment, or does it just start one?

Paragraphs: It’s not clear what it would mean for one paragraph to contain another. Change the parser so that a document like <p>hello<p>world</p> results in two sibling paragraphs instead of one paragraph inside another; real browsers do this too.

Scripts: JavaScript code embedded in a <script> tag uses the left angle bracket to mean less-than. Modify your lexer so that the contents of <script> tags are treated specially: no tags are allowed inside <script>, except the </script> close tag.Technically it’s just </script followed by a space, tab, \v, \r, slash, or greater than sign. If you need to talk about </script> tags inside JavaScript code, you have to split it into multiple strings.

Quoted attributes: Quoted attributes can contain spaces and right angle brackets. Fix the lexer so that this is supported properly. Hint: the current lexer is a finite state machine, with two states (determined by in_tag). You’ll need more states.

Syntax Highlighting: Implement the view-source: protocol as in Chapter 1, but make it syntax-highlight the source code of HTML pages. Keep source code for HTML tags in a normal font, but make text contents bold. If you’ve implemented it, wrap text in <pre> tags as well to preserve line breaks. Hint: subclass the HTML parser and use it to implement your syntax highlighter.

So far, layout has been a linear process that handles open tags and close tags independently. But web pages are trees, and look like them: borders and backgrounds visually nest inside one another. To support that, this chapter switches to tree-based layout, where the tree of elements is transformed into a tree of layout objects for the visual elements of the page. In the process, we’ll make our web pages more colorful with backgrounds.

The layout tree

Right now, our browser lays out an element’s open and close tags separately. Both tags modify global state, like the cursor_x and cursor_y variables, but they aren’t otherwise connected, and information about the element as a whole, like its width and height, is never computed. That makes it pretty hard to draw a background color behind text. So web browsers structure layout differently.

In a browser, layout is about producing a layout tree, whose nodes are layout objects, each associated with an HTML element,Elements like <script> don’t generate layout objects, and some elements generate multiple (<li> elements have a layout object for the bullet point!), but mostly it’s one layout object each. and each with a size and a position. The browser walks the HTML tree to produce the layout tree, then computes the size and position for each layout object, and finally draws each layout object to the screen.

Let’s start by looking how the existing Layout class is used:

class Browser:
    def load(self, url):
        # ...
        self.display_list = Layout(self.nodes).display_list
        #...

Here, a Layout object is created briefly and then thrown away. Let’s instead make it the beginning of our layout tree by storing it in a Browser field:

class Browser:
    def load(self, url):
        # ...
        self.document = Layout(self.nodes)
        self.document.layout()
        self.display_list = self.document.display_list
        #...

Note that I’ve renamed the Layout constructor to a layout method, so that constructing a layout object and actually laying it out can be different steps. The constructor now just stores the node it was passed:

class Layout:
    def __init__(self, node):
        self.node = node

So far, we still don’t have a tree—we just have a single Layout object. To make it into a tree, we’ll need add child and parent pointers. I’m also going to add a pointer to the previous sibling, because that’ll be useful for computing sizes and positions later:

class Layout:
    def __init__(self, node, parent, previous):
        self.node = node
        self.parent = parent
        self.previous = previous
        self.children = []

That said, requiring a parent and previous element now makes it tricky to construct a Layout object in Browser, since the root of the layout tree obviously can’t have a parent. To rectify that, let me add a second kind of layout object to serve as the root of the layout tree.I don’t want to just pass None for the parent, because the root layout object also computes its size and position differently, as we’ll see later this chapter. I think of that root as the document itself, so let’s call it DocumentLayout:

class DocumentLayout:
    def __init__(self, node):
        self.node = node
        self.parent = None
        self.children = []

    def layout(self):
        child = Layout(self.node, self, None)
        self.children.append(child)
        child.layout()
        self.display_list = child.display_list

Note an interesting thing about this new layout method: its role is to create the child layout objects, and then recursively call its children’s layout methods. This is a common pattern for constructing trees, and we’ll be seeing it a lot throughout this book.

Now when we construct a DocumentLayout object inside load, we’ll be building a tree! A very short tree, more of a stump for now, but it’s something!

By the way, since we now have DocumentLayout, let’s rename Layout so it’s less ambiguous. I like BlockLayout as a name, because we ultimately want Layout to represent a block of text, like a paragraph or a heading:

class BlockLayout:
    # ...

Make sure to rename the Layout constructor call in DocumentLayout as well. Test your browser and make sure that after all of these refactors, everything still works.

Block layout

So far, we’ve focused on text layout—and text is laid out horizontally in lines.In European languages, at least! But web pages are really constructed out of larger blocks, like headings, paragraphs, and menus, that are stacked vertically one after another. We need to add support for this kind of layout to our browser, and the way we’re going to do that involves expanding on the layout tree we’ve already built.

The core idea is that we’ll have a whole tree of BlockLayout objects (with a DocumentLayout at the root). Some will represent leaf blocks that contain text, and they’ll lay out their contents the way we’ve already implemented. But there will also be new, intermediate BlockLayouts with BlockLayout children, and they will stack their children vertically.

To create these intermediate BlockLayout children, we can use a loop like this:

class BlockLayout:
    def layout_intermediate(self):
        previous = None
        for child in self.node.children:
            next = BlockLayout(child, self, previous)
            self.children.append(next)
            previous = next

I’ve called this method layout_intermediate, but only so you can add it to the code right away and then compare it with the existing recurse method.

This code is tricky, so read it carefully. It involves two trees: the HTML tree, which node and child point to; and the layout tree, which self, previous, and next point to. The two trees have similar structure, so it’s easy to get confused. But remember that this code constructs the layout tree from the HTML tree, so it reads from node.children (in the HTML tree) and writes to self.children (in the layout tree).

So we have two ways to lay out an element: either calling recurse and flush, or this layout_intermediate function. To determine which one a layout object should use, we’ll need to know what kind of content its HTML node contains: text and text-related tags like <b>, or blocks like <p> and <h1>. That function looks something like this:

class BlockLayout:
    def layout_mode(self):
        if isinstance(self.node, Text):
            return "inline"
        elif self.node.children:
            if any([isinstance(child, Element) and \
                    child.tag in BLOCK_ELEMENTS
                    for child in self.node.children]):
                return "block"
            else:
                return "inline"
        else:
            return "block"

Here the list of BLOCK_ELEMENTS is basically what you expect, a list of all the tags that describe parts of a page instead of formatting:Taken from the HTML living standard.

BLOCK_ELEMENTS = [
    "html", "body", "article", "section", "nav", "aside",
    "h1", "h2", "h3", "h4", "h5", "h6", "hgroup", "header",
    "footer", "address", "p", "hr", "pre", "blockquote",
    "ol", "ul", "menu", "li", "dl", "dt", "dd", "figure",
    "figcaption", "main", "div", "table", "form", "fieldset",
    "legend", "details", "summary"
]

Our layout_mode method has to handle one tricky case, where a node contains both block children like a <p> element but also text children like a text node or a <b> element. I’ve chosen to use block mode in this case, but it’s probably best to think of this as a kind of error on the part of the web developer. And just like with implicit tags in Chapter 4, we use a repair mechanism to make sense of the situation.In real browsers, that repair mechanism is called “anonymous block boxes” and is more complex than what’s described here.

So now BlockLayout can determine what kind of layout to do based on the layout_mode of its HTML node:

class BlockLayout:
    def layout(self):
        mode = self.layout_mode()
        if mode == "block":
            previous = None
            for child in self.node.children:
                next = BlockLayout(child, self, previous)
                self.children.append(next)
                previous = next
        else:
            self.cursor_x = 0
            self.cursor_y = 0
            self.weight = "normal"
            self.style = "roman"
            self.size = 16

            self.line = []
            self.recurse(self.node)
            self.flush()

Finally, since BlockLayouts can now have children, the layout method next needs to recursively call layout so those children can construct their children, and so on recursively:

class BlockLayout:
    def layout(self):
        # ...
        for child in self.children:
            child.layout()

We also need to gather their display_list fields into a single array:

class BlockLayout:
    def layout(self):
        # ...
        for child in self.children:
            self.display_list.extend(child.display_list)

Our browser is now constructing a whole tree of BlockLayout objects; in fact, if you add a print_tree call to Browser’s load method, you’ll see that large web pages like this chapter produce large and complex layout trees!

Oh, you might also notice that the text on these web pages is now totally unreadable, because it’s all overlapping at the top of the page. Let’s fix that next.

Size and position

In the previous chapter, the Layout object was responsible for the whole web page, so it just laid out its content starting at the top of the page. Now that we have multiple BlockLayout objects each containing a different paragraph of text, we’re going to need to do things a little differently, computing a size and position for each layout object independently.

Let’s start with cursor_x and cursor_y. Instead of having them denote absolute positions on the page, let’s make them relative to the BlockLayout itself; they now need to start from 0 instead of HSTEP and VSTEP, both in layout and flush:

class BlockLayout:
    def layout(self):
        else:
            self.cursor_x = 0
            self.cursor_y = 0

    def flush(self):
        # ...
        self.cursor_x = 0
        # ...

Since these fields are now relative, we’ll need to add the block’s x and y position in flush when computing the display list:

class BlockLayout:
    def flush(self):
        # ...
        for rel_x, word, font in self.line:
            x = self.x + rel_x
            y = self.y + baseline - font.metrics("ascent")
            self.display_list.append((x, y, word, font))
        # ...

Similarly, to wrap lines, we can’t compare cursor_x to WIDTH, because cursor_x is a relative measure while WIDTH is an absolute measure; instead, we’ll wrap lines when cursor_x reaches the block’s width:

class BlockLayout:
    def word(self, word):
        # ...
        if self.cursor_x + w > self.width:
            # ...
        # ...

So now that leaves us with the problem of computing these x, y, and width fields. Let’s recall that BlockLayouts represent blocks of text like paragraphs or headings, and are stacked vertically one atop another. That means each one starts at its parent’s left edge:

class BlockLayout:
    def layout(self):
        self.x = self.parent.x
        # ...

Its vertical position depends on the position and height of their previous sibling. If there is no previous sibling, they start at the parent’s top edge:

class BlockLayout:
    def layout(self):
        if self.previous:
            self.y = self.previous.y + self.previous.height
        else:
            self.y = self.parent.y
        # ...

Note that in each of these cases, to compute one block’s x and y, the x and y of its parent block must already have been computed. That means these computations have to go before the recursive layout call, so those children can compute their x and y based on this block’s x and y. Similarly, since the y position of a block depends on its previous sibling’s y position, the recursive layout calls have to start at the first sibling and iterate through the list forward—which is how we’ve already done it, but which will be an important constraint in later chapters.

Now we’ll need compute widths and heights. Width is easy: blocks are as wide as their parents:In the next chapter, we’ll add support for author-defined styles, which in real browsers modify these layout rules by setting custom widths or changing how x and y position are computed.

class BlockLayout:
    def layout(self):
        self.width = self.parent.width
        # ...

Height, meanwhile, is a little tricky. A BlockLayout that contains other blocks should be tall enough to contain all of its children, so its height should be the sum of its children’s heights:

class BlockLayout:
    def layout(self):
        # ...
        if mode == "block":
            self.height = sum([
                child.height for child in self.children])

However, a BlockLayout that contains text doesn’t have children; instead, it needs to be tall enough to contain all its text, which we can conveniently read off of cursor_y:Since the height is just equal to cursor_y, why not rename cursor_y to height instead? You could, it would work fine, but I would rather not. As you can see from, say, the y computation, the height field is a public field, read by other layout objects to compute their positions. As such I’d rather make sure it always has the right value, whereas cursor_y changes as we lay out a paragraph of text and therefore sometimes has the “wrong” value. Keeping these two fields separate avoids a whole class of nasty bugs where the height field is read “too soon” and therefore gets the wrong value.

class BlockLayout:
    def layout(self):
        # ...
        else:
            self.height = self.cursor_y

Let’s think again about dependencies. Height has the opposite dependencies compared to x, y, and width: the height of a block depends on its children’s heights. While x, y, and width must be computed before the recursive call, height has to be computed after, at the very end of layout.

Finally, even DocumentLayout needs some layout code, though since the document always starts in the same place it’s pretty simple:

class DocumentLayout:
    def layout(self):
        # ...
        self.width = WIDTH - 2*HSTEP
        self.x = HSTEP
        self.y = VSTEP
        child.layout()
        self.height = child.height + 2*VSTEP

Note that there’s some padding around the contents—HSTEP on the left and right, and VSTEP above and below. That’s so the text won’t run into the very edge of the window and get cut off.

For all three types of layout object, the order of the steps in the layout method should be the same:

• When layout is called, it first computes the width, x, and y fields, reading from the parent and previous layout objects.
• Next, it creates a child layout object for each child element.
• Then, the child layout nodes are recursively laid out by calling their layout methods.
• Finally, layout computes the height field, reading from the child layout objects.

You can see these steps in action in this widget:

This kind of dependency reasoning is crucial to layout and more broadly to any kind of computation on trees. If you get the order of operations wrong, some layout object will try to read a value that hasn’t been computed yet, and the browser will have a bug. We’ll come back to this issue of dependencies later, where it will become even more important.

Anyway, with all of the sizes and positions now computed correctly, you should see the browser now correctly display all of the text on the page.

Recursive painting

Our layout method is now doing quite a bit of work: computing sizes and positions; creating child layout objects; recursively laying out those child layout objects; and aggregating the display lists so the text can be drawn to the screen. This is a bit messy, so let’s take a moment to extract just one part of this, the display list part. Along the way, we can stop copying the display list contents over and over again as we go up the layout tree.

I think it’s most convenient to do that by adding a paint function to each layout object, which appends any of its own layout objects to the display list and then recursively paints the child layouts. A neat trick here is to pass the list itself as an argument, and have the recursive function append to that list. For DocumentLayout, which only has one child, the recursion looks like this:

class DocumentLayout:
    def paint(self, display_list):
        self.children[0].paint(display_list)

You can now delete the line that computes a DocumentLayout’s display_list field.

For a BlockLayout with multiple children, paint is called on each child:

class BlockLayout:
    def paint(self, display_list):
        for child in self.children:
            child.paint(display_list)

Again, delete the line that computes a BlockLayout’s display_list field by copying from child layout objects.

Finally for a BlockLayout object with text inside, we need to copy over the display_list field that it computes during recurse and flush:

class BlockLayout:
    def paint(self, display_list):
        display_list.extend(self.display_list)

Now the browser can use paint to collect its own display_list variable:

class Browser:
    def load(self, url):
        # ...
        self.display_list = []
        self.document.paint(self.display_list)
        self.draw()

Check it out: your browser is now using fancy tree-based layout! I recommend pausing to test and debug. Tree-based layout is powerful but complex, and we’re about to add more features. Stable foundations make for comfortable houses.

Backgrounds

Browsers use the layout tree a lot,For example, in Chapter 7, we’ll use the size and position of each link to figure out which one the user clicked on. and one simple and visually compelling use case is drawing backgrounds.

Backgrounds are rectangles, so our first task is putting rectangles in the display list. Conceptually, the display list contains commands, and we want two types of commands:

class DrawText:
    def __init__(self, x1, y1, text, font):
        self.top = y1
        self.left = x1
        self.text = text
        self.font = font
    
class DrawRect:
    def __init__(self, x1, y1, x2, y2, color):
        self.top = y1
        self.left = x1
        self.bottom = y2
        self.right = x2
        self.color = color

Now BlockLayout must add DrawText objects to the display list:Why not change the display_list field inside an BlockLayout to contain DrawText commands directly? I suppose you could, but I think it’s cleaner this way, with all of the draw commands created in one place.

class BlockLayout:
    def paint(self, display_list):
        for x, y, word, font in self.display_list:
            display_list.append(DrawText(x, y, word, font))
        # ...

Note that we must add the block’s x and y, since the positions in the display list are relative to the block’s position.

But it can also add DrawRect commands for backgrounds. Let’s add a gray background to pre tags (which are used for code examples):

class BlockLayout:
    def paint(self, display_list):
        if isinstance(self.node, Element) and self.node.tag == "pre":
            x2, y2 = self.x + self.width, self.y + self.height
            rect = DrawRect(self.x, self.y, x2, y2, "gray")
            display_list.append(rect)
        # ...

Make sure this code comes before the loop that adds DrawText objects and before the recursion into child layout objects: the background has to be drawn below and therefore before any contents. This is again a kind of dependency reasoning with tree traversals!

With the display list filled out, we need the paint method to run each graphics command. Let’s add an execute method for this. On DrawText it calls create_text:

class DrawText:
    def execute(self, scroll, canvas):
        canvas.create_text(
            self.left, self.top - scroll,
            text=self.text,
            font=self.font,
            anchor='nw',
        )

Note that execute takes the scroll amount as a parameter; this way, each graphics command does the relevant coordinate conversion itself. DrawRect does the same with create_rectangle:

class DrawRect:
    def execute(self, scroll, canvas):
        canvas.create_rectangle(
            self.left, self.top - scroll,
            self.right, self.bottom - scroll,
            width=0,
            fill=self.color,
        )

By default, create_rectangle draws a one-pixel black border, which for backgrounds we don’t want, so make sure to pass width = 0:

We still want to skip offscreen graphics commands, so let’s add a bottom field to DrawText so we know when to skip those:

def __init__(self, x1, y1, text, font):
    # ...
    self.bottom = y1 + font.metrics("linespace")

The browser’s draw method now just uses top and bottom to decide which commands to execute:

class Browser:
    def draw(self):
        self.canvas.delete("all")
        for cmd in self.display_list:
            if cmd.top > self.scroll + HEIGHT: continue
            if cmd.bottom < self.scroll: continue
            cmd.execute(self.scroll, self.canvas)

Try your browser on a page—maybe this one—with code snippets on it. You should see each code snippet set off with a gray background.

Here’s one more cute benefit of tree-based layout. Thanks to tree-based layout we now record the height of the whole page. The browser can use that to avoid scrolling past the bottom of the page:

def scrolldown(self, e):
    max_y = max(self.document.height - HEIGHT, 0)
    self.scroll = min(self.scroll + SCROLL_STEP, max_y)
    self.draw()

So those are the basics of tree-based layout! In fact, as we’ll see in the next two chapters, this is just part of the layout tree’s role in the browser. But before we get to that, we need to add some styling capabilities to our browser.

Summary

This chapter was a dramatic rewrite of your browser’s layout engine:

• Layout is now tree-based and produces a layout tree
• Each node in the tree has one of two different layout modes
• Layout computes a size and position for each layout object
• The display list now contains generic commands
• Plus, source code snippets now have backgrounds

Tree-based layout makes it possible to dramatically expand our browser’s styling capabilities. We’ll work on that in the next chapter.

Outline

The complete set of functions, classes, and methods in our browser should look something like this:

Exercises

Links Bar: At the top and bottom of each chapter of this book is a gray bar naming the chapter and offering back and forward links. It is enclosed in a <nav class="links"> tag. Have your browser give this links bar the light gray background a real browser would.

Hidden Head: There’s a good chance your browser is still showing scripts, styles, and page titles at the top of every page you visit. Make it so that the <head> element and its contents are never displayed. Those elements should still be in the HTML tree, but not in the layout tree.

Bullets: Add bullets to list items, which in HTML are <li> tags. You can make them little squares, located to the left of the list item itself. Also indent <li> elements so the text inside the element is to the right of the bullet point.

Scrollbar: At the right edge of the screen, draw a blue, rectangular scrollbar. The ratio of its height to the screen height should be the same as the ratio of the screen height to the document height, and its location should reflect the position of the screen within the document. Hide the scrollbar if the whole document fits onscreen.

Table of Contents: This book has a table of contents at the top of each chapter, enclosed in a <nav id="toc"> tag, which contains a list of links. Add the text “Table of Contents”, with a gray background, above that list. Don’t modify the lexer or parser.

Anonymous block boxes: Sometimes, an element has a mix of text-like and container-like children. For example, in this HTML,

<div><i>Hello, </i><b>world!</b><p>So it began...</p></div>

the <div> element has three children: the <i>, <b>, and <p> elements. The first two are text-like; the last is container-like. This is supposed to look like two paragraphs, one for the <i> and <b> and the second for the <p>. Make your browser do that. Specifically, modify BlockLayout so it can be passed a sequence of sibling nodes, instead of a single node. Then, modify the algorithm that constructs the layout tree so that any sequence of text-like elements gets made into a single BlockLayout.

Run-ins: A “run-in heading” is a heading that is drawn as part of the next paragraph’s text.The exercise names in this section could be considered run-in headings. But since browser support for the display: run-in property is poor, this book actually doesn’t use it; the headings are actually embedded in the next paragraph. Modify your browser to render <h6> elements as run-in headings. You’ll need to implement the previous exercise on anonymous block boxes, and then add a special case for <h6> elements.

In the last chapter, we gave each pre element a gray background. It looks OK, and it is good to have defaults… but of course sites want a say in how they look. Websites do that with Cascading Style Sheets, which allow web authors (and, as we’ll see, browser developers) to define how a web page ought to look.

Parsing with functions

One way a web page can change its appearance is with the style attribute. For example, this changes an element’s background color:

<div style="background-color:lightblue"></div>

More generally, a style attribute contains property/value pairs separated by semicolons. The browser looks at those property-value pairs to determine how an element looks, for example to determine its background color.

To add this to our browser, we’ll need to start by parsing these property/value pairs. I’ll use recursive parsing functions, which are a good way to build a complex parser step by step. The idea is that each parsing function advances through the text being parsed and returns the data it parsed. We’ll have different functions for different types of data, and organize them in a CSSParser class that stores the text being parsed and the parser’s current position in it:

class CSSParser:
    def __init__(self, s):
        self.s = s
        self.i = 0

Let’s start small and build up. A parsing function for whitespace increments the index i past every whitespace character:

def whitespace(self):
    while self.i < len(self.s) and self.s[self.i].isspace():
        self.i += 1

Whitespace is insignificant, so there’s no data to return in this case. On the other hand, we’ll want to return property names and values when we parse them:

def word(self):
    start = self.i
    while self.i < len(self.s):
        if self.s[self.i].isalnum() or self.s[self.i] in "#-.%":
            self.i += 1
        else:
            break
        if not (self.i > start):
            raise Exception("Parsing error")
        
        return self.s[start:self.i]

This function increments i through any word characters,I’ve chosen the set of word characters here to cover property names (which use letters and the dash), numbers (which use the minus sign, numbers, periods), units (the percent sign), and colors (which use the hash sign). Real CSS values have a more complex syntax but this is enough for our toy browser. much like whitespace. But to return the parsed data, it stores where it started and extracts the substring it moved through.

Parsing functions can fail. The word function we just wrote raises an exception if i hasn’t advanced though at least one character—otherwise it didn’t point at a word to begin with.You can add error text to the exception-raising code, too; I recommend doing that to help you debug problems. Likewise, to check for a literal colon (or some other punctuation character) you’d do this:

def literal(self, literal):
    if not (self.i < len(self.s) and self.s[self.i] == literal):
        raise Exception("Parsing error")
    self.i += 1

The great thing about parsing functions is that they can build on one another. For example, property-value pairs are a property, a colon, and a value,In reality properties and values have different syntaxes, so using word for both isn’t quite right, but for our browser’s limited CSS this simplification will do. with whitespace in between:

def pair(self):
    prop = self.word()
    self.whitespace()
    self.literal(":")
    self.whitespace()
    val = self.word()
    return prop.lower(), val

We can parse sequences by calling parsing functions in a loop. For example, style attributes are a sequence of property-value pairs:

def body(self):
    pairs = {}
    while self.i < len(self.s):
        prop, val = self.pair()
        pairs[prop.lower()] = val
        self.whitespace()
        self.literal(";")
        self.whitespace()
    return pairs

Now, in a browser, we always have to think about handling errors. Sometimes a web page author makes a mistake; sometimes our browser doesn’t support a feature some other browser does. So we should skip property-value pairs that don’t parse, but keep the ones that do.

We can skip things with this little function; it stops at any one of a set of characters, and returns that character (or None if it was stopped by the end of the file):

def ignore_until(self, chars):
    while self.i < len(self.s):
        if self.s[self.i] in chars:
            return self.s[self.i]
        else:
            self.i += 1

When we fail to parse a property-value pair, we either skip to the next semicolon or to the end of the string:

def body(self):
    # ...
    while self.i < len(self.s):
        try:
            # ...
        except Exception:
            why = self.ignore_until([";"])
            if why == ";":
                self.literal(";")
                self.whitespace()
            else:
                break
    # ...

Skipping parse errors is a double-edged sword. It hides error messages, making it harder for authors to debug their style sheets; it also makes it harder to debug your parser.I suggest removing the try block when debugging. So in most programming situations this “catch-all” error handling is a code smell.

But “catch-all” error handling has an unusual benefit on the web. The web is an ecosystem of many browsers,And an ecosystem of many browser versions, some of which haven’t been written yet—but need to be supported as best we can. which (for example) support different kinds of property values.Our browser does not support parentheses in property values, for example, which real browsers use for things like the calc and url functions. CSS that parses in one browser might not parse in another. With silent parse errors, browsers just ignore stuff they don’t understand, and web pages mostly work in all of them. The principle (variously called “Postel’s Law”,After a line in the specification of TCP, written by Jon Postel the “Digital Principle”,After a similar idea in circuit design, where transistors must be nonlinear to reduce analog noise. or the “Robustness Principle”) is: produce maximally conformant output but accept even minimally conformant input.

The style attribute

Now that the style attribute is parsed, we can use that parsed information in the rest of the browser. We’ll store the parsed information in a style field on each node:

def style(node):
    node.style = {}
    # ...
    for child in node.children:
        style(child)

Call style in the browser’s load method, after parsing the HTML but before doing layout.

This style function will also fill in the style field by parsing the element’s style attribute:

def style(node):
    # ...
    if isinstance(node, Element) and "style" in node.attributes:
        pairs = CSSParser(node.attributes["style"]).body()
        for property, value in pairs.items():
            node.style[property] = value
    # ...

With the style information stored on each element, the browser can consult it for styling information:

class BlockLayout:
    def paint(self, display_list):
        bgcolor = self.node.style.get("background-color",
                                      "transparent")
        if bgcolor != "transparent":
            x2, y2 = self.x + self.width, self.y + self.height
            rect = DrawRect(self.x, self.y, x2, y2, bgcolor)
            display_list.append(rect)
        # ...

I’ve removed the default gray background from pre elements for now, but we’ll put it back soon.

Open this chapter up in your browser to test your code: the code block right after this paragraph should now have a light blue background.

<div style="background-color:lightblue"> ... </div>

So this is one way web pages can change their appearance. And in the early days of the web,I’m talking Netscape 3. The late 90s. something like this was the only way. But honestly, it’s a pain—you need to set a style attribute on each element, and if you change the style that’s a lot of attributes to edit. CSS was invented to improve on this state of affairs:

• One CSS file can consistently style many web pages at once
• One line of CSS can consistently style many elements at once
• CSS is future-proof and supports browsers with different features

To achieve these goals, CSS extends the style attribute with two related ideas: selectors and cascading. Selectors describe which HTML elements a list of property/value pairs apply to:CSS rules can also be guarded by “media queries”, which say that a rule should apply only in certain browsing environments (like only on mobile or only in landscape mode). Media queries are super-important for building sites that work across many devices, like reading this book on a phone.

selector { property-1: value-1; property-2: value-2; }

Since one of these rules can apply to many elements, it’s possible for several rules to apply to the same element. So browsers have a cascading mechanism to resolve conflicts in favor of the most specific rule. Cascading also means a browser can ignore rules it doesn’t understand and choose the next-most-specific rule that it does understand.

So next, let’s add support for CSS to our browser. We’ll need to parse CSS files into selectors and property/value pairs; figure out which elements on the page match each selector; and then copy those property values to the elements’ style fields.

Selectors

Selectors come in lots of types, but in our browser, we’ll support two: tag selectors (p selects all <p> elements, ul selects all <ul> elements) and descendant selectors (article div selects all div elements with an article ancestor).The descendant selector associates to the left; in other words, a b c means a c that descends from a b that descends from an a, which maybe you’d write (a b) c if CSS had parentheses.

We’ll have a class for each type of selector to store the selector’s contents, like the tag name for a tag selector:

class TagSelector:
    def __init__(self, tag):
        self.tag = tag

Each selector class will also test whether the selector matches an element:

    def matches(self, node):
        return isinstance(node, Element) and self.tag == node.tag

A descendant selector works similarly. It has two parts, which are both themselves selectors:

class DescendantSelector:
    def __init__(self, ancestor, descendant):
        self.ancestor = ancestor
        self.descendant = descendant

Then the match method is recursive (and bottoms out at, say, a TagSelector):

class DescendantSelector:
    def matches(self, node):
        if not self.descendant.matches(node): return False
        while node.parent:
            if self.ancestor.matches(node.parent): return True
            node = node.parent
        return False

Now, to create these selector objects, we need a parser. In this case, that’s just another parsing function:Once again, using word here for tag names is actually not quite right, but it’s close enough. One tricky side effect of using word is that a class name selector (like .main) or an identifier selector (like #signup) is mis-parsed as a tag name selector. But that won’t cause any harm since there aren’t any elements with those tags.

def selector(self):
    out = TagSelector(self.word().lower())
    self.whitespace()
    while self.i < len(self.s) and self.s[self.i] != "{":
        tag = self.word()
        descendant = TagSelector(tag.lower())
        out = DescendantSelector(out, descendant)
        self.whitespace()
    return out

A CSS file is just a sequence of selectors and blocks:

def parse(self):
    rules = []
    while self.i < len(self.s):
        self.whitespace()
        selector = self.selector()
        self.literal("{")
        self.whitespace()
        body = self.body()
        self.literal("}")
        rules.append((selector, body))
    return rules

Once again, let’s pause to think about error handling. First, when we call body while parsing CSS, we need it to stop when it reaches a closing brace:

def body(self):
    # ...
    while self.i < len(self.s) and self.s[self.i] != "}":
        try:
            # ...
        except Exception:
            why = self.ignore_until([";", "}"])
            if why == ";":
                self.literal(";")
                self.whitespace()
            else:
                break
    # ...

Second, there might also be an parse error while parsing a selector. In that case, we want to skip the whole rule:

def parse(self):
    # ...
    while self.i < len(self.s):
        try:
            # ...
        except Exception:
            why = self.ignore_until(["}"])
            if why == "}":
                self.literal("}")
                self.whitespace()
            else:
                break
    # ...

Error handling is hard to get right, so make sure to test your parser, just like the HTML parser two chapters back. Here are some errors you might run into:

• If the output is missing some rules or properties, it’s probably a bug being hidden by error handling. Remove some try blocks and see if the error in question can be fixed.

• If you’re seeing extra rules or properties that are mangled versions of the correct ones, you probably forgot to update i somewhere.

• If you’re seeing an infinite loop, check whether the error-handling code always increases i. Each parsing function (except whitespace) should always increment i.

You can also add a print statement to the start and endIf you print an open parenthesis at the start of the function and a close parenthesis at the end, you can use your editor’s “jump to other parenthesis” feature to skip through output quickly. of each parsing function with the name of the parsing function,If you also add the right number of spaces to each line it’ll be a lot easier to read. Don’t neglect debugging niceties like this! the index i,It can be especially helpful to print, say, the 20 characters around index i from the string. and the parsed data. It’s a lot of output, but it’s a sure-fire way to find really complicated bugs.

Applying style sheets

With the parser debugged, the next step is applying the parsed style sheet to the web page. Since each CSS rule can style many elements on the page, this will require looping over all elements and all rules. When a rule applies, its property/values pairs are copied to the element’s style information:

def style(node, rules):
    # ...
    for selector, body in rules:
        if not selector.matches(node): continue
        for property, value in body.items():
            node.style[property] = value

Make sure to put this loop before the one that parses the style attribute: the style attribute should override style sheet values.

To try this out, we’ll need a style sheet. Every browser ships with a browser style sheet,Technically called a “User Agent” style sheet. User Agent, like the Memex. which defines its default styling for the various HTML elements. For our browser, it might look like this:

pre { background-color: gray; }

Let’s store that in a new file, browser.css, and have our browser read it when it starts:

class Browser:
    def __init__(self):
        # ...
        with open("browser.css") as f:
            self.default_style_sheet = CSSParser(f.read()).parse()

Now, when the browser loads a web page, it can apply that default style sheet to set up its default styling for each element:

def load(self, url):
    # ...
    rules = self.default_style_sheet.copy()
    style(self.nodes, rules)
    # ...

The browser style sheet is the default for the whole web. But each web site can also use CSS to set a consistent style for the whole site. by referencing CSS files using link elements:

<link rel="stylesheet" href="/main.css">

The mandatory rel attribute identifies this link as a style sheetFor browsers, stylesheet is the most important kind of link, but there’s also preload for loading assets that a page will use later and icon for identifying favicons. Search engines also use these links; for example, rel=canonical names the “true name” of a page and search engines use it to track pages that appear at multiple URLs. and the href attribute has the style sheet URL. We need to find all these links, download their style sheets, and apply them.

Since we’ll be doing similar tasks in the next few chapters, let’s generalize a bit and write a recursive function that turns a tree into a list of nodes:

def tree_to_list(tree, list):
    list.append(tree)
    for child in tree.children:
        tree_to_list(child, list)
    return list

I’ve written this helper to work on both HTML and layout tree, for later. We can use tree_to_list with a Python list comprehensionIt’s kind of crazy, honestly, that Python lets you write things like this—crazy, but very convenient! to grab the URL of each linked style sheet:

def load(self, url):
    # ...
    links = [node.attributes["href"]
             for node in tree_to_list(self.nodes, [])
             if isinstance(node, Element)
             and node.tag == "link"
             and "href" in node.attributes
             and node.attributes.get("rel") == "stylesheet"]
    # ...

Now, these style sheet URLs are usually not full URLs; they are something called relative URLs, such as:There are other flavors, including query-relative and scheme-relative URLs, that I’m skipping.

• A normal URL, which specifies a scheme, host, path, and so on;
• A host-relative URL, which starts with a slash but reuses the existing scheme and host; or
• A path-relative URL, which doesn’t start with a slash and is resolved like a file name would be.

To download the style sheets, we’ll need to convert each relative URL into a full URL:

class URL:
    def resolve(self, url):
        if "://" in url: return URL(url)
        if not url.startswith("/"):
            dir, _ = self.path.rsplit("/", 1)
            while url.startswith("../"):
                _, url = url.split("/", 1)
                if "/" in dir:
                    dir, _ = dir.rsplit("/", 1)
            url = dir + "/" + url
        return URL(self.scheme + "://" + self.host + \
                   ":" + str(self.port) + url)

Note the logic for handling .. in the relative URL; for whatever reason, this is handled by the browser, not the server.

Now the browser can request each linked style sheet and add its rules to the rules list:

def load(self, url):
    # ...
    for link in links:
        try:
            header, body = url.resolve(link).request()
        except:
            continue
        rules.extend(CSSParser(body).parse())

The try/except ignores style sheets that fail to download, but it can also hide bugs in your code, so if something’s not right try removing it temporarily.

Cascading

A web page can now have any number of style sheets applied to it. And since two rules can apply to the same element, rule order matters: it determines which rules take priority, and when one rule overrides another.

In CSS, the correct order is called cascade order, and it is based on the rule’s selector, with file order as a tie breaker. This system allows more specific rules to override more general ones, so that you can have a browser style sheet, a site-wide style sheet, and maybe a special style sheet for a specific web page, all co-existing.

Since our browser only has tag selectors, our cascade order just counts them:

class TagSelector:
    def __init__(self, tag):
        # ...
        self.priority = 1

class DescendantSelector:
    def __init__(self, ancestor, descendant):
        # ...
        self.priority = ancestor.priority + descendant.priority

Then our cascade order for rules is just those priorities:

def cascade_priority(rule):
    selector, body = rule
    return selector.priority

Now when we call style, we need to sort the rules, like this:

def load(self, url):
    # ...
    style(self.nodes, sorted(rules, key=cascade_priority))
    # ...

Note that before sorting rules, it is in file order. Since Python’s sorted function keeps the relative order of things when possible, file order thus acts as a tie breaker, as it should.

That’s it: we’ve added CSS to our web browser! I mean—for background colors. But there’s more to web design than that. For example, if you’re changing background colors you might want to change foreground colors as well—the CSS color property. But there’s a catch: color affects text, and there’s no way to select a text node. How can that work?

Inherited styles

The way text styles work in CSS is called inheritance. Inheritance means that if some node doesn’t have a value for a certain property, it uses its parent’s value instead. That includes text nodes. Some properties are inherited and some aren’t; it depends on the property. Background color isn’t inherited, but text color and other font properties are.

Let’s implement inheritance for four font properties: color, font-weight (normal or bold), font-style (normal or italic), and font-size (a length or percentage).

Let’s start by listing our inherited properties and their default values:

INHERITED_PROPERTIES = {
    "font-size": "16px",
    "font-style": "normal",
    "font-weight": "normal",
    "color": "black",
}

We’ll then add the actual inheritance code to the style function. It has to come before the other loops, since explicit rules should override inheritance:

def style(node, rules):
    # ...
    for property, default_value in INHERITED_PROPERTIES.items():
        if node.parent:
            node.style[property] = node.parent.style[property]
        else:
            node.style[property] = default_value
    # ...

Inheriting font size comes with a twist. Web pages can use percentages as font sizes: h1 { font-size: 150% } makes headings 50% bigger than surrounding text. But what if you had, say, a code element inside an h1 tag—would that inherit the 150% value for font-size? Surely it shouldn’t be another 50% bigger than the rest of the heading text?

So, in fact, browsers resolve percentages to absolute pixel units before storing them in the style and before those values are inherited; it’s called a “computed style”.Full CSS is a bit more confusing: there are specified, computed, used, and actual values, and they affect lots of CSS properties besides font-size. We’re just not implementing those other properties in this book. Of the properties our toy browser supports, only font-size needs to be computed in this way:

def style(node, rules):
    # ...
    if node.style["font-size"].endswith("%"):
        # ...

    for child in node.children:
        style(child, rules)

Resolving percentage sizes has just one tricky edge case: percentage sizes for the root html element. In that case the percentage is relative to the default font size:This code has to parse and unparse font sizes because our style field stores strings; in a real browser the computed style is stored parsed so this doesn’t have to happen.

def style(node, rules):
    # ...
    if node.style["font-size"].endswith("%"):
        if node.parent:
            parent_font_size = node.parent.style["font-size"]
        else:
            parent_font_size = INHERITED_PROPERTIES["font-size"]
        node_pct = float(node.style["font-size"][:-1]) / 100
        parent_px = float(parent_font_size[:-2])
        node.style["font-size"] = str(node_pct * parent_px) + "px"

Note that this happens after all of the different sources of style values are handled (so we are working with the final font-size value) but before we recurse (so children can assume our font-size has been resolved to a pixel value).

Font Properties

So now with all these font properties implemented, let’s change layout to use them! That will let us move our default text styles to the browser style sheet:

a { color: blue; }
i { font-style: italic; }
b { font-weight: bold; }
small { font-size: 90%; }
big { font-size: 110%; }

The browser looks up font information in BlockLayout’s word method; we’ll need to change it to use the node’s style field, and for that, we’ll need to pass in the node itself:

class BlockLayout:
    def recurse(self, node):
        if isinstance(node, Text):
            for word in node.text.split():
                self.word(node, word)
        else:
            # ...

    def word(self, node, word):
        font = self.get_font(node)
        # ...

Here, the get_font method is a simple wrapper around our font cache:

class BlockLayout:
    def get_font(self, node):
        weight = node.style["font-weight"]
        style = node.style["font-style"]
        if style == "normal": style = "roman"
        size = int(float(node.style["font-size"][:-2]) * .75)
        return get_font(size, weight, style)

Note that for font-style we need to translate CSS “normal” to Tk “roman” and for font-size we need to convert CSS pixels to Tk points.

Text color requires a bit more plumbing. First, we have to read the color and store it in the current line:

def word(self, node, word):
    color = node.style["color"]
    # ...
    self.line.append((self.cursor_x, word, font, color))
    # ...