Java Generics and Collections, 2nd Edition (Maurice Naftalin, Philip Wadler, Stuart Marks) (Z-Library)

Java Generics and Collections SECOND EDITION Fundamentals and Recommended Practices Maurice Naftalin and Philip Wadler with Stuart Marks

Java Generics and Collections by Maurice Naftalin and Philip Wadler Copyright © 2025 Morningside Light. All rights reserved. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com). For more information, contact our corporate/institutional sales department: 800- 998-9938 or corporate@oreilly.com. Acquisitions Editor: Brian Guerin Development Editor: Sara Hunter Production Editor: Aleeya Rahman Copyeditor: Rachel Head Proofreader: Piper Content Partners Indexer: nSight, Inc. Cover Designer: Karen Montgomery Cover Illustrator: José Marzan Jr. Interior Designer: David Futato Interior Illustrator: Kate Dullea June 2025: Second Edition

Revision History for the Second Edition 2025-06-17: First Release See http://oreilly.com/catalog/errata.csp? isbn=9781098136727 for release details. The O’Reilly logo is a registered trademark of O’Reilly Media, Inc. Java Generics and Collections, the cover image, and related trade dress are trademarks of O’Reilly Media, Inc. The views expressed in this work are those of the authors and do not represent the publisher’s views. While the publisher and the authors have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the authors disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights. 978-1-098-13672-7 [LSI]

Dedication We dedicate this book to Joyce Naftalin, Lionel Naftalin, Adam Wadler, and Leora Wadler —Maurice Naftalin and Philip Wadler

Preface The second edition of this book is a comprehensive update for Java 21. Since a major impetus for writing it was the introduction of sequenced collections and the earlier impact of streams and lambdas, I expected before starting work that the major changes needed would be in Part II, principally as a result of the introduction of sequenced collections. However, that was a serious underestimate of the changes that Java has undergone in the last 20 years: in fact, many revisions to Part I were also required. The language has changed; it now supports records, local variable type inference, pattern-matching expressions, and generic types in type comparison expressions. Also, most examples in Part I needed updating to take account of changes in the platform libraries, including the current deprecation of the Integer constructors, static methods on the Comparator interface, and the introduction of unmodifiable collections and of streams. An important motivation for writing a second edition was to record some of the insights gained by the Java community in the use of both generics and collections since 2005. These are mainly contained in a retrospective section (“On the Design of Java Generics”) and two new collections chapters: Chapter 17, which provides guidance for use of the Collections Framework, and Chapter 18, which reviews the most crucial— and also the most controversial— decisions underlying the choices made in the design of the framework. In addition, the chapters on reification (Chapter 5) and effective generics (Chapter 7) have been substantially rewritten, the chapter on design patterns has

been dropped, and the chapter on migration from pre- generic code has been made available online as an Appendix for technical and historical interest. I have preserved the preface to the first edition, in an updated form, at the end of this section. I thought this was worthwhile to convey some of the sense of excitement that accompanied the finely coordinated collection of features with which Java 5 brought the Java language into the 21st century. Maurice Naftalin Edinburgh, February 2025 Acknowledgments for the Second Edition First, I want to thank all those people who, having read the first edition, nonetheless encouraged me to embark on a revision. Support from the Java community sustained this project throughout; I think myself very fortunate to be part of such a warm and supportive community. At O’Reilly, Zan McQuade provided invaluable help in building the case for publishing the new edition. As my editor, Sara Hunter was always supportive and encouraging when it was most needed. My copy editor, Rachel Head, had a remarkable sixth sense for detecting technical problems. My production editor, Aleeya Rahman, worked valiantly to remove the many small but crucial bugs in the text. One satisfying aspect of writing a later edition is to be able to correct the errors in an earlier one (while trying to avoid introducing too many new ones). Amongst the people who

identified errata in the first edition were Valentin Baca, Thomas Costick, Svein Egil Nilsen, Emanuel Frua, Anders Granlund, Ravindra Ranwala, Randolf Rothfuss, Jan de Ruiter, and Christopher Sahnwaldt. I’m grateful to the many people who gave their time to reviewing this book, providing corrections and helpful ideas, both small and large, in some cases giving extremely generously of their time. They include Mohamed Anees, Larry Cable, Ray Djajadinata, Brian Goetz, Mary Gouseti, Andrzej Grzesik, George Heineman, Cay Horstmann, Timmy Jose, Heinz Kabutz, Marc Loy, Chris Newland, Scott Oaks, Simon Park, José Paumard, Simon Ritter, Robert Scholte, Daniel Shaya, Ivan Šipka, Fred Smith, Tushar Srivastava, and Jens-Hagen Syrbe. Of course, all remaining errors and omissions are mine alone. I’m very happy to repeat, 19 years later, the first edition’s recommendation of Heinz Kabutz’s The Java Specialists’ Newsletter, still going strong after 325 editions! My greatest pleasure is to acknowledge that many of the ideas in this revision were developed in collaboration with Stuart Marks. They were refined in many long discussions and joint presentations. His experience, knowledge, and encouragement made him the best technical editor any author could wish for. Phil Wadler has been a good friend throughout. Love as ever to Ben, Daniel, Isaac, Joe, and Ruth. Intended Audience This book is intended for everyone who knows something about Java and would like to find out more. It’s not a Java tutorial, so we assume knowledge of basic Java concepts

like classes, static and instance methods, and so on. We use the syntax of Java 21, but most syntax features associated specifically with generics are explained in the text. If you are having difficulty understanding the syntax of a particular code sample, you may find that your integrated development environment (IDE) can offer helpful refactoring suggestions that will clarify its purpose. We assume very basic knowledge of the Collections API. If you have written any programs using ArrayList or HashSet, you should have no difficulty. When discussing the behavior of particular collection classes and methods, we often refer to the Javadoc. When in doubt, the Javadoc provides the definitive specification. Obtaining the Example Programs The sample code for this edition is available as a Maven project at https://github.com/MauriceNaftalin/JGC_2e_Book_Code. Note that some of the code in the project fails to compile, for reasons given in the corresponding text. If you have a technical question or a problem using the code examples, please send email to support@oreilly.com. You may use the sample code in your programs and documentation. You do not need to contact O’Reilly Media for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example

code from this book into your product’s documentation does require permission. We appreciate, but generally do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Java Generics and Collections, 2nd Edition, by Maurice Naftalin and Philip Wadler (O’Reilly). Copyright 2025 Morningside Light, 978-1-098-13672-7.” If you feel your use of code examples falls outside fair use or the permission given here, feel free to contact us at permissions@oreilly.com. Conventions Used in This Book We use the following font and format conventions for code: Code is shown in constant width font, with boldface used for emphasis: class InnocentClient { public static void main(String[] args) { List<Integer>[] intLists = DeceptiveLibrary.createIntLists(1); List<? extends Number>[] numLists = intLists; numLists[0] = List.of(1.01); int i = intLists[0].get(0); // class cast exception! } } We often include code that corresponds to the body of an appropriate main method:

List<Integer>[] intLists = DeceptiveLibrary.createIntLists(1); List<? extends Number>[] numLists = intLists; numLists[0] = List.of(1.01); int i = intLists[0].get(0); // class cast exception! In the code repository, these fragments are assembled into main methods. Often, multiple fragments are assembled into the same class. Note that not all classes in the repository compile correctly; the explanation for the compile errors will be found in the corresponding text. Code fragments—including program elements such as variable or function names, databases, data types, environment variables, statements, and keywords— are printed in constant width font when they appear within a paragraph (as when we referred to a main method in the preceding item). We omit imports from the text. Necessary imports are included in the repository code. Sample interactive sessions, showing command-line input and corresponding output, are shown in constant width font, with user-supplied input preceded by a percent sign: % javac g/Stack.java g/ArrayStack.java g/Stacks.java l/Client.java Note: Client.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.

Sometimes we show a snippet of a JShell session, with the prompt and user input followed by the JShell output: jshell> List.of("Larry", "Curly", "Larry", "Moe") $2 ==> [Larry, Curly, Larry, Moe] When user-supplied input extends over two lines, the first line is ended with a backslash: % javac -Xlint:unchecked g/Stack.java g/ArrayStack.java \ % g/Stacks.java l/Client.java l/Client.java:4: warning: [unchecked] unchecked call to push(E) as a member of the raw type Stack for (int i = 0; i<4; i++) stack.push(new Integer(i)); New terms, URLs, email addresses, filenames, and file extensions are set in italics. Constant width italic shows text that should be replaced with user-supplied values or by values determined by context. NOTE This element signifies a general note. Assertions We clarify our code by liberal use of the assert statement. Our expectation is that assertions will be enabled. They are not enabled by default, so to obtain the expected behavior you must enable them by invoking the Java virtual machine

(JVM) with the -ea or -enableassertions flag. Each occurrence of assert is followed by a boolean expression that is expected to evaluate to true. If assertions are enabled and the expression evaluates to false, an AssertionError is thrown, including an indication of where the error occurred. We only write assertions that we expect to evaluate to true. Since assertions may not be enabled, an assertion should never have side effects upon which any non- assertion code depends. When checking for a condition that might not hold (such as confirming that the arguments to a method call are valid), we use a conditional and throw an exception explicitly. O’Reilly Online Learning NOTE For more than 40 years, O’Reilly Media has provided technology and business training, knowledge, and insight to help companies succeed. Our unique network of experts and innovators share their knowledge and expertise through books, articles, and our online learning platform. O’Reilly’s online learning platform gives you on-demand access to live training courses, in- depth learning paths, interactive coding environments, and a vast collection of text and video from O’Reilly and 200+ other publishers. For more information, visit https://oreilly.com.

How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 800-889-8969 (in the United States or Canada) 707-827-7019 (international or local) 707-829-0104 (fax) support@oreilly.com https://oreilly.com/about/contact.html We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at https://oreil.ly/java-generics-and-collections2e. For news and information about our books and courses, visit https://oreilly.com. Find us on LinkedIn: https://linkedin.com/company/oreilly- media. Watch us on YouTube: https://youtube.com/oreillymedia.

Preface to the First Edition The introduction of generics to the Java language, accompanied at the same time by other improvements, has transformed the experience of programming in Java. The most immediate effect is in the use of the collection types, such as List. You could always use these classes to collect objects of different types—for example, String or Integer —but generics has added to this flexibility the capability to restrict, in a precise way, the type that a collection should contain, and to enforce this restriction. Say you wish to process lists. Some may be lists of integers, others lists of strings, and yet others lists of lists of strings. In Java before generics, this was simple. You could represent all three by the same class, called List, which has elements of class Object: list of integers List list of strings List list of lists of strings List In order to keep the language simple, you were forced to do some of the work yourself: you had to keep track of the fact that you had a list of integers (or strings or lists of strings), and when you extracted an element from the list you had to cast it from Object back to Integer (or String or List). The Collections Framework before generics made extensive use of this idiom. As Einstein said, “Everything should be as simple as possible but no simpler.”1 And some might say the

approach above is too simple. In Java with generics, you may distinguish different types of lists: list of integers List<Integer> list of strings List<String> list of lists of strings List<List<String>> Now the compiler keeps track of whether you have a list of integers (or strings or lists of strings), and no explicit cast back to Integer (or String or List<String>) is required. In some ways, this is similar to generics in Ada or templates in C++, but the actual inspiration is parametric polymorphism as found in functional languages such as ML and Haskell. Part I of this book provides a thorough introduction to generics. We discuss the interactions between generics and subtyping, and how to use wildcards and bounds; we describe techniques for evolving your code; we explain subtleties connected with casts and arrays; we treat advanced topics such as the interaction between generics and security, and how to maintain binary compatibility; and we update common design patterns to exploit generics. The introduction of generics into Java has sparked some controversy. Certainly, the design of generics involved trade-offs: making code evolution easy requires that objects should not reify compile-time information about generic type parameters—that is, should not preserve this information for use at run time—but its absence at run time introduces corner cases into operations such as casting and array creation. We present a balanced treatment of

generics, explaining how to exploit their strengths and work around their weaknesses. Part II provides a comprehensive introduction to the Collections Framework. The English polymath Isaac Newton (1675) wrote, “If I have seen further, it is by standing on the shoulders of giants.” The best programmers live by this motto, building on existing frameworks and reusable code wherever appropriate. The Java Collections Framework provides reusable interfaces and implementations for a number of common collection types, including lists, sets, queues, and maps.2 Compared to pre-generic code, generic code using collections is easier to read and the compiler catches more type errors. Further, collections provide excellent illustrations of the use of generics. One might say that generics and collections were made for each other, and, indeed, ease of use of collections was one of the main reasons for introducing generics in the first place. In Part II, we describe the entire Collections Framework from first principles in order to help you use collections more effectively. The design of generics for Java is influenced by a number of previous proposals—notably, GJ, by Bracha et al. (1998); the addition of wildcards to GJ, proposed by Igarashi and Viroli (2006); and further development of wildcards by Torgersen et al. (2004). Design of generics was carried out under the Java Community Process by a team led by Bracha and including Odersky, Thorup, and Wadler (as parts of JSR 14 and JSR 201). Odersky’s GJ compiler formed the basis of the original javac compiler for generics.

Acknowledgments for the First Edition The folks at Oracle, and previously at Sun Microsystems, were fantastically good about answering our questions. They were always happy to explain a tricky point or mull over a design trade-off. Thanks to Joshua Bloch, Gilad Bracha, Martin Buchholz, Joseph D. Darcy, Neal M. Gafter, Mark Reinhold, David Stoutamire, Scott Violet, and Peter von der Ahé. It has been a pleasure to work with the following researchers, who contributed to the design of generics for Java: Erik Ernst, Christian Plesner Hansen, Atsushi Igarashi, Martin Odersky, Mads Torgersen, and Mirko Viroli. We received comments and help from a number of people. Thanks to Brian Goetz, David Holmes, Heinz M. Kabutz, Deepti Kalra, Angelika Langer, Stefan Liebeg, Doug Lea, Tim Munro, Steve Murphy, and C K Shibin. We enjoyed reading Heinz M. Kabutz’s The Java Specialists’ Newsletter and Angelika Langer’s Java Generics FAQ, both available online. Our editor, Michael Loukides, was always ready with good advice. Paul C. Anagnostopoulos of Windfall Software turned our LaTeX into camera-ready copy, and Jeremy Yallop produced the index. Our families kept us sane (and insane). Love to Adam, Ben, Catherine, Daniel, Isaac, Joe, Leora, Lionel, and Ruth. 1 This is the popular paraphrase: what Einstein actually said was that theory should be as simple as possible “without having to surrender the

adequate representation of a single datum of experience” (Calaprice 2011, 384–5). The pre-generics code above clearly fails this test: it fails to represent an important aspect of reality, namely the type of the objects to be contained in the List. 2 Of course, not all programmers are so respectful of their predecessors’ work. Sometimes, as Richard Hamming said of computer scientists, “Instead of standing on each other’s shoulders, we stand on each other’s toes.”

Part I. Generics Generics are a powerful, and sometimes controversial, feature of the Java programming language. This part of the book describes generics, using the Collections Framework as a source of examples. A comprehensive introduction to the Collections Framework appears in the second part of the book. The first four chapters focus on the fundamentals of generics. Chapter 1 gives an overview of generic types and methods. Chapter 2 reviews how subtyping works and explains how wildcards let you use subtyping in connection with generics. Chapter 3 describes how generics work with the Comparable interface, which requires a notion of bounds on type variables. Chapter 4 looks at how generics work with various declarations, including constructors, static members, and nested classes. Once you have these four chapters under your belt, you will be able to use generics effectively in most basic situations. The next three chapters treat advanced topics. Chapter 5 explains how the same design that leads to ease of evolution also necessarily leads to a few rough edges in the treatment of casts, exceptions, and arrays. The fit between generics and arrays is the worst rough corner of the language, and we formulate two principles to help you work around the problems. Chapter 6 explains features that relate generics and reflection, including the type Class<T> and additions to the Java library that support reflection of generic types. Chapter 7 contains advice on how to use