قراءة كود لم تكتبه وتتبّعه
في هذا الدرس 11 موضوعات
هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.
Lesson Overview
Last lesson you learned that generated code is a draft and that you must be able to explain every line before you use it. This lesson shows you how to get that understanding: by reading the code in two passes and tracing it by hand with a small input.
You already know hand-tracing from BEG-016 (the variable table) and the debugger from BEG-018. Here you apply both to code you did not write, which is a different skill from tracing your own: you do not know the author's intent, so you must work out the behaviour from the code and compare it with the requirement.
Why this matters: a quick read finds the idea. Only a trace finds the off-by-one error that hides inside a reasonable-looking loop. The same technique is how you review a teammate's pull request and how you read code in a project you have just joined.
The next lesson, "Testing generated code against the requirement", turns what you find by tracing into automated tests.
Learning Objectives
By the end of this lesson you will be able to:
- Read generated code in two passes: first for the idea, then line by line.
- Build a trace table and use it to compute what the code returns for a small input.
- Choose the inputs to trace: a typical case, the empty case, one item, and the last item.
- Spot hidden loops (such as
containsinside a loop) and estimate the cost of the code. - Write one sentence per block of code and use the gaps to find what you do not yet understand.
Written Explanation
Pass 1: read for the idea
Read the method once from top to bottom without judging details. Ask three questions:
- What goes in (parameters and their types)? What comes out (the return type)?
- What is the general plan: a loop that accumulates? A search that stops early? A comparison?
- Does the plan match the requirement you wrote?
If the plan does not match the requirement, stop here. The draft is wrong at the design level, and no tracing will fix it.
Pass 2: trace with a small input
Now act as the computer. Pick a small input, so that you can finish by hand, and write a trace table: one row per step, one column per variable, recording each value after that step. The table is the same tool as in BEG-016.
Rules that keep a trace honest:
- Write values down; do not keep them in your head. Your head will "autocorrect" the code into what you expect it to say.
- Follow the code literally, including the loop's start value, its condition, and its update.
- Record the loop condition when it becomes false. Many bugs live in the last check.
- Compare the final result with what the requirement says, not with what the code seems to want.
Which inputs to trace
A single typical input is not enough. Trace these four kinds, using the smallest example of each:
| Input | Why |
|---|---|
| A typical case | Confirms the main plan |
Empty input ([], "") | Does the loop run zero times? What is returned? |
| One item | Often the first and the last item at once, so both ends are tested together |
| The item at the edge (first or last) | Catches loops that start late or stop early |
For numeric rules (limits, ages, balances), also trace the boundary value itself: the exact limit, one below it, and one above it. This is the equivalence-class and boundary idea from BEG-045, applied to reading.
Check the cost: look for hidden loops
Complexity (BEG-039) is easy to miss in a draft because the method call looks like a single step. Some methods hide a loop inside:
list.contains(x)andlist.indexOf(x)walk the list one by one, so they cost O(n). The Java documentation forListwarns that its search methods can be costly linear searches in many implementations.
So contains inside a loop over n items is a loop inside a loop: O(n²). Count the loops, and for each call ask "does this walk the whole collection?". HashSet.contains is the exception, because hashing (BEG-041) makes it O(1) on average.
One sentence per block
After tracing, write one sentence per block of code, in your own words: "This loop visits each item once", "this if counts only positive items", "this line stops at the first match". Where you cannot write the sentence, you have found something you do not yet understand. Resolve each gap with the documentation, the debugger, or a question to the assistant (checked afterwards, as in BEG-056) before you use the code.
Examples
Example 1: a trace table finds an off-by-one error (simple)
Requirement: countPositives(int[] a) returns how many items are greater than 0. The draft:
static int countPositives(int[] a) {
int c = 0;
for (int i = 1; i < a.length; i++)
if (a[i] > 0) c++;
return c;
}Pass 1: a counting loop; the plan matches. Pass 2: trace [5, -1, 2].
| Step | i | a[i] | a[i] > 0 ? | c |
|---|---|---|---|---|
| start | 0 | |||
| 1 | 1 | -1 | no | 0 |
| 2 | 2 | 2 | yes | 1 |
| check | 3 | 3 < 3 is false, stop | 1 |
The code returns 1, but the requirement says 2 (the items 5 and 2). The table shows why: i starts at 1, so a[0] is never looked at. Running the method confirmed it: 1. The fix is int i = 0.
The edge inputs agree: [] returns 0 (correct by luck), and [9] returns 0 (wrong: it should be 1).
Example 2: tracing a rule at its boundary (practical)
Requirement: a library member may borrow another book only if they currently have fewer than the limit of books and have no unpaid fine. The draft:
static boolean canBorrow(int borrowed, int limit, boolean hasFine) {
return borrowed <= limit && !hasFine;
}Pass 1: one condition with two parts; it matches the structure of the rule. Pass 2: trace the boundary values with a limit of 3 and no fine.
| borrowed | borrowed <= 3 | !hasFine | Returns | Requirement says |
|---|---|---|---|---|
| 2 | true | true | true | true |
| 3 | true | true | true | false (already at the limit) |
| 4 | false | true | false | false |
Only the exact-limit row exposes the bug. Running canBorrow(3, 3, false) returned true. The fix is borrowed < limit. Reading "less-or-equal limit" casually sounds fine; only comparing the boundary row with the requirement exposes it.
Example 3: a hidden loop (realistic)
Requirement: hasDuplicate(List<Integer> xs) returns true if any value appears twice. The draft:
static boolean hasDuplicate(List<Integer> xs) {
List<Integer> seen = new ArrayList<>();
for (int x : xs) {
if (seen.contains(x)) return true;
seen.add(x);
}
return false;
}Sentence per block: "The loop visits each value. If the value is already in seen, return true. Otherwise remember it. Reaching the end means no duplicate." The answers are correct on [4, 8, 4] (true) and [4, 8, 5] (false).
The cost question: seen.contains(x) walks seen, which grows by one each iteration. For n distinct values the number of comparisons is about 0 + 1 + 2 + ... + (n - 1), which is about n²/2: O(n²). We measured it on a 100,000-item list with no duplicates:
ArrayList version: 6305 ms
HashSet version: 29 msThese times are from one run on our machine and will differ on yours, but the gap will be large. The better draft keeps the same plan with a HashSet:
static boolean hasDuplicate(List<Integer> xs) {
Set<Integer> seen = new HashSet<>();
for (int x : xs) {
if (!seen.add(x)) return true; // add returns false if already present
}
return false;
}Set.add returns false when the value was already there, so one call both checks and records. Total cost: O(n) on average, at the price of O(n) extra memory.
Backend Insight
Backends often handle lists with thousands or millions of items: orders, users, log lines. A hidden O(n²) loop that is invisible with ten test rows can make an endpoint time out in production. Reading for loops inside loops is therefore a standard step in code review, and it matters even more for generated code, because assistants often produce the simple, familiar version first.
Tracing also prepares you for debugging. When a production defect is reported, the first job is to reconstruct what the code did for one specific input, which is exactly a trace. The debugger from BEG-018 does the table for you; the skill is knowing which input to trace and what the answer should have been.
Common Mistakes
Mistake 1: Tracing what you think the code says
- Incorrect: reading
i = 1as "start at the first item" because that is what the idea suggests. - Correct: writing
i = 1in the table and then noticing thata[1]is the second item.
Always copy the literal start value, condition, and update into the table.
Mistake 2: Only tracing the typical case
A typical input passes most buggy drafts. Add the empty case, one item, and the edge item. For rules with a limit, trace the exact limit.
Mistake 3: Ignoring hidden loops
contains and indexOf look like one step but each walks the collection. Count them as loops when you estimate the cost.
Exercises
Level A: Foundation
A1. Trace this method on [2, 3, 4] with a table, and give the result.
static int product(int[] a) {
int p = 1;
for (int x : a) p *= x;
return p;
}أظهر الحل A1
A1. Trace: p starts at 1; after 2 it is 2; after 3 it is 6; after 4 it is 24. Result: 24 (we ran it: 24). The empty array would return 1, which is the "empty product"; whether that is acceptable depends on the requirement, so check it.
A2. For a method lastItem(int[] a) that returns the final item of an array, list the four kinds of input you would trace.
أظهر الحل A2
A2. A typical case (several items), the empty array (there is no last item: the requirement must say what happens), one item (first and last at once), and the case where the last item is not the largest or smallest (to check that the method really returns the last item and not an extreme).
A3. What is the complexity of this method, and where is the hidden loop?
static List<String> unique(List<String> in) {
List<String> out = new ArrayList<>();
for (String s : in)
if (!out.contains(s)) out.add(s);
return out;
}أظهر الحل A3
A3. O(n²) in the worst case. The hidden loop is out.contains(s), which walks out on every iteration.
Level B: Application
B1. Requirement: countBig(int[] a, int limit) counts the items that are at least limit. The draft:
static int countBig(int[] a, int limit) {
int c = 0;
for (int x : a) if (x > limit) c++;
return c;
}Trace [5, 7] with limit 5. What is the result, and what should it be? Fix the method.
أظهر الحل B1
B1. 5 > 5 is false, 7 > 5 is true, so c is 1. The requirement says 2, because 5 is "at least" 5. Running it printed 1. The fix is x >= limit.
B2. Requirement: findLast(int[] a, int t) returns the index of the last occurrence of t, or -1. Trace the draft on [4, 7, 4] with t = 4, and name the line that causes the problem.
static int findLast(int[] a, int t) {
int idx = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == t) { idx = i; break; }
}
return idx;
}أظهر الحل B2
B2. Index 0: a[0] == 4, so idx = 0 and break leaves the loop. The method returns 0, but the last occurrence is index 2 (we ran it: 0). The break is the problem: remove it, and the loop keeps overwriting idx until the end. (Or loop backwards from the end and return at the first match.)
B3. Write one sentence for each block of unique from A3. Then write a faster version in the same shape.
أظهر الحل B3
B3. Example: "Make an empty result list. For each string in the input: if it is not already in the result, add it. Return the result." The fast version keeps the output order and uses a set for the membership test:
static List<String> unique(List<String> in) {
List<String> out = new ArrayList<>();
Set<String> seen = new HashSet<>();
for (String s : in)
if (seen.add(s)) out.add(s);
return out;
}Level C: Challenge
C1. Requirement: isSorted(int[] a) returns true if the items are in ascending order (equal neighbours allowed). Trace the draft on [1, 5, 3] and on [1, 2, 3]. What is wrong, and why does it only show on some inputs?
static boolean isSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) return false;
else return true;
}
return true;
}أظهر الحل C1
C1. For [1, 5, 3]: i = 0, 1 > 5 is false, so the else runs and the method returns true immediately. It should return false, because 5 > 3. For [1, 2, 3] it also returns true, correctly, by luck (we ran both: true and true). The else return true ends the method after the first pair, so only the first pair is ever checked. It looks right on sorted inputs and on inputs where the first pair is out of order. Remove the else branch so that return true happens only after the loop.
C2. A draft for "does any pair of items add up to sum?" uses two nested loops over all pairs (i, j) with j > i. For an array of 1,000 items, how many pairs does it check in the worst case? Describe a faster approach using a HashSet, and state its complexity.
أظهر الحل C2
C2. 1,000 × 999 / 2 = 499,500 pairs, which is O(n²). A faster approach: walk the array once; for each item x, check whether sum - x is already in a HashSet, then add x to the set. Each step is O(1) on average, so the total is O(n) average time with O(n) extra memory.
Mini Challenge
Write your own small buggy method (for example, "returns the second item", "counts vowels in a string", or "returns the last index of a letter") with one deliberate off-by-one or boundary mistake. Give it to a classmate, or put it away for a day, then:
- Write the requirement in one or two sentences.
- Trace it with a table on a typical input, on
[]or"", and on the edge case. - Write one sentence per block.
- Estimate the cost by counting loops, including hidden ones.
Check your work: your table follows the literal code, the buggy row is visible in it, and your sentences explain every block without hand-waving.
Summary & Next Lesson
Key takeaways
- Read generated code twice: once for the idea, then line by line with a small input.
- A trace table records the values of the variables after each step. Write values down and follow the code literally.
- Trace the typical case, empty input, one item, and the edge item. For limits, trace the exact boundary.
- Look for hidden loops such as
containsinside a loop; they turn O(n) plans into O(n²). - One sentence per block shows what you do not yet understand.
Next lesson
The next lesson, "Testing generated code against the requirement", shows how to turn those traced inputs into automated tests that you write before looking at the generated code.
Self-check
- What does a trace table record?
- Why trace an empty input and a one-item input?
- What is the hidden loop in
list.contains(x)inside aforloop, and what is the resulting complexity? - In Example 2, which input exposed the bug, and why?
- Why compare a trace result with the requirement and not with the code's intent?
أظهر الإجابات
- The value of each variable after each step.
- The empty input checks whether the loop runs zero times and what is returned; one item is the first and the last item at once, so both ends are tested.
containswalks the collection, so it is a loop inside the loop; the result is O(n²).- The exact-limit input (3 books at a limit of 3):
<=accepts it, but the requirement says "fewer than". - The code's intent is whatever the draft happens to do, bugs included; the requirement is the standard for being correct.
References
- Oracle, Java SE 21
ListAPI. It states that the search methods ofListsuch ascontainsandindexOfcan be costly linear searches in many implementations. - The timings in Example 3 and every program output in this lesson come from compiling and running the code with JDK 21 on one machine; the O(1)-average cost of
HashSet.containsis taught in BEG-041 and was not re-verified here against a source.
التطبيق
طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.
تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.