Root/
Source at commit 190bcaf982869388b508a0a4c97cff62fbb73038 created 13 years 11 months ago. By werner, Added a topological sort algorithm, for use when dumping. | |
---|---|
1 | /* |
2 | * obj.c - Object definition model |
3 | * |
4 | * Written 2009, 2010 by Werner Almesberger |
5 | * Copyright 2009, 2010 by Werner Almesberger |
6 | * |
7 | * This program is free software; you can redistribute it and/or modify |
8 | * it under the terms of the GNU General Public License as published by |
9 | * the Free Software Foundation; either version 2 of the License, or |
10 | * (at your option) any later version. |
11 | */ |
12 | |
13 | |
14 | #include <stdlib.h> |
15 | #include <string.h> |
16 | #include <assert.h> |
17 | |
18 | #include "util.h" |
19 | #include "error.h" |
20 | #include "expr.h" |
21 | #include "meas.h" |
22 | #include "inst.h" |
23 | #include "hole.h" |
24 | #include "layer.h" |
25 | #include "delete.h" |
26 | #include "obj.h" |
27 | |
28 | |
29 | #define DEFAULT_SILK_WIDTH make_mil(15) /* @@@ */ |
30 | #define DEFAULT_OFFSET make_mil(0) /* @@@ */ |
31 | |
32 | #define MAX_ITERATIONS 1000 /* abort "loop"s at this limit */ |
33 | |
34 | |
35 | char *pkg_name = NULL; |
36 | struct frame *frames = NULL; |
37 | struct frame *root_frame = NULL; |
38 | struct frame *active_frame = NULL; |
39 | void *instantiation_error = NULL; |
40 | |
41 | |
42 | /* ----- Searching --------------------------------------------------------- */ |
43 | |
44 | |
45 | /* |
46 | * @@@ Known bug: we should compare all parameters of an instance, not just the |
47 | * object's base or the vectors end. |
48 | */ |
49 | |
50 | static int found = 0; |
51 | static int search_suspended = 0; |
52 | static const struct vec *find_vec = NULL; |
53 | static const struct obj *find_obj = NULL; |
54 | static struct coord find_pos; |
55 | |
56 | |
57 | static void suspend_search(void) |
58 | { |
59 | search_suspended++; |
60 | } |
61 | |
62 | static void resume_search(void) |
63 | { |
64 | assert(search_suspended > 0); |
65 | search_suspended--; |
66 | } |
67 | |
68 | |
69 | static struct coord get_pos(const struct inst *inst) |
70 | { |
71 | return inst->obj ? inst->base : inst->u.vec.end; |
72 | } |
73 | |
74 | |
75 | void find_inst(const struct inst *inst) |
76 | { |
77 | struct coord pos; |
78 | |
79 | if (search_suspended) |
80 | return; |
81 | if (find_vec != inst->vec) |
82 | return; |
83 | if (find_obj != inst->obj) |
84 | return; |
85 | pos = get_pos(inst); |
86 | if (pos.x != find_pos.x || pos.y != find_pos.y) |
87 | return; |
88 | found++; |
89 | } |
90 | |
91 | |
92 | void search_inst(const struct inst *inst) |
93 | { |
94 | find_vec = inst->vec; |
95 | find_obj = inst->obj; |
96 | find_pos = get_pos(inst); |
97 | } |
98 | |
99 | |
100 | /* ----- Get the list of anchors of an object ------------------------------ */ |
101 | |
102 | |
103 | int obj_anchors(struct obj *obj, struct vec ***anchors) |
104 | { |
105 | anchors[0] = &obj->base; |
106 | switch (obj->type) { |
107 | case ot_frame: |
108 | return 1; |
109 | case ot_rect: |
110 | case ot_line: |
111 | anchors[1] = &obj->u.rect.other; |
112 | return 2; |
113 | case ot_pad: |
114 | anchors[1] = &obj->u.pad.other; |
115 | return 2; |
116 | case ot_hole: |
117 | anchors[1] = &obj->u.hole.other; |
118 | return 2; |
119 | case ot_meas: |
120 | anchors[1] = &obj->u.meas.high; |
121 | return 2; |
122 | case ot_arc: |
123 | /* |
124 | * Put end point first so that this is what we grab if dragging |
125 | * a circle (thereby turning it into an arc). |
126 | */ |
127 | anchors[1] = &obj->u.arc.end; |
128 | anchors[2] = &obj->u.arc.start; |
129 | return 3; |
130 | default: |
131 | abort(); |
132 | } |
133 | } |
134 | |
135 | |
136 | /* ----- Instantiation ----------------------------------------------------- */ |
137 | |
138 | |
139 | static int generate_frame(struct frame *frame, struct coord base, |
140 | const struct frame *parent, struct obj *frame_ref, int active); |
141 | |
142 | |
143 | struct num eval_unit(const struct expr *expr, const struct frame *frame); |
144 | /*static*/ struct num eval_unit(const struct expr *expr, const struct frame *frame) |
145 | { |
146 | struct num d; |
147 | |
148 | d = eval_num(expr, frame); |
149 | if (!is_undef(d) && to_unit(&d)) |
150 | return d; |
151 | fail_expr(expr); |
152 | return undef; |
153 | } |
154 | |
155 | |
156 | static struct num eval_unit_default(const struct expr *expr, |
157 | const struct frame *frame, struct num def) |
158 | { |
159 | if (expr) |
160 | return eval_unit(expr, frame); |
161 | to_unit(&def); |
162 | return def; |
163 | } |
164 | |
165 | |
166 | static int generate_vecs(struct frame *frame, struct coord base) |
167 | { |
168 | struct coord vec_base; |
169 | struct vec *vec; |
170 | struct num x, y; |
171 | |
172 | for (vec = frame->vecs; vec; vec = vec->next) { |
173 | x = eval_unit(vec->x, frame); |
174 | if (is_undef(x)) |
175 | goto error; |
176 | y = eval_unit(vec->y, frame); |
177 | if (is_undef(y)) |
178 | goto error; |
179 | vec_base = vec->base ? vec->base->pos : base; |
180 | vec->pos = vec_base; |
181 | vec->pos.x += x.n; |
182 | vec->pos.y += y.n; |
183 | if (!inst_vec(vec, vec_base)) |
184 | goto error; |
185 | meas_post(vec, vec->pos); |
186 | } |
187 | return 1; |
188 | |
189 | error: |
190 | instantiation_error = vec; |
191 | return 0; |
192 | } |
193 | |
194 | |
195 | static int generate_objs(struct frame *frame, struct coord base, int active) |
196 | { |
197 | struct obj *obj; |
198 | char *name; |
199 | int ok; |
200 | struct num width, offset; |
201 | |
202 | for (obj = frame->objs; obj; obj = obj->next) |
203 | switch (obj->type) { |
204 | case ot_frame: |
205 | if (!generate_frame(obj->u.frame.ref, |
206 | obj->base ? obj->base->pos : base, frame, obj, |
207 | active && obj->u.frame.ref->active_ref == obj)) |
208 | return 0; |
209 | break; |
210 | case ot_line: |
211 | width = eval_unit_default(obj->u.line.width, frame, |
212 | DEFAULT_SILK_WIDTH); |
213 | if (is_undef(width)) |
214 | goto error; |
215 | if (!inst_line(obj, obj->base ? obj->base->pos : base, |
216 | obj->u.line.other ? obj->u.line.other->pos : base, |
217 | width.n)) |
218 | goto error; |
219 | break; |
220 | case ot_rect: |
221 | width = eval_unit_default(obj->u.rect.width, frame, |
222 | DEFAULT_SILK_WIDTH); |
223 | if (is_undef(width)) |
224 | goto error; |
225 | if (!inst_rect(obj, obj->base ? obj->base->pos : base, |
226 | obj->u.rect.other ? obj->u.rect.other->pos : base, |
227 | width.n)) |
228 | goto error; |
229 | break; |
230 | case ot_pad: |
231 | name = expand(obj->u.pad.name, frame); |
232 | if (!name) |
233 | goto error; |
234 | ok = inst_pad(obj, name, |
235 | obj->base ? obj->base->pos : base, |
236 | obj->u.pad.other ? obj->u.pad.other->pos : base); |
237 | free(name); |
238 | if (!ok) |
239 | goto error; |
240 | break; |
241 | case ot_hole: |
242 | if (!inst_hole(obj, obj->base ? obj->base->pos : base, |
243 | obj->u.hole.other ? obj->u.hole.other->pos : base)) |
244 | goto error; |
245 | break; |
246 | case ot_arc: |
247 | width = eval_unit_default(obj->u.arc.width, frame, |
248 | DEFAULT_SILK_WIDTH); |
249 | if (is_undef(width)) |
250 | goto error; |
251 | if (!inst_arc(obj, obj->base ? obj->base->pos : base, |
252 | obj->u.arc.start ? obj->u.arc.start->pos : base, |
253 | obj->u.arc.end ? obj->u.arc.end->pos : base, |
254 | width.n)) |
255 | goto error; |
256 | break; |
257 | case ot_meas: |
258 | assert(frame == root_frame); |
259 | offset = eval_unit_default(obj->u.meas.offset, frame, |
260 | DEFAULT_OFFSET); |
261 | if (is_undef(offset)) |
262 | goto error; |
263 | inst_meas_hint(obj, offset.n); |
264 | break; |
265 | default: |
266 | abort(); |
267 | } |
268 | return 1; |
269 | |
270 | error: |
271 | instantiation_error = obj; |
272 | return 0; |
273 | } |
274 | |
275 | |
276 | static int generate_items(struct frame *frame, struct coord base, int active) |
277 | { |
278 | char *s; |
279 | int ok; |
280 | |
281 | if (!frame->name) { |
282 | s = expand(pkg_name, frame); |
283 | inst_select_pkg(s); |
284 | free(s); |
285 | } |
286 | inst_begin_active(active && frame == active_frame); |
287 | ok = generate_vecs(frame, base) && generate_objs(frame, base, active); |
288 | inst_end_active(); |
289 | return ok; |
290 | } |
291 | |
292 | |
293 | static int run_loops(struct frame *frame, struct loop *loop, |
294 | struct coord base, int active) |
295 | { |
296 | struct num from, to; |
297 | int n; |
298 | int found_before, ok; |
299 | |
300 | if (!loop) |
301 | return generate_items(frame, base, active); |
302 | from = eval_num(loop->from.expr, frame); |
303 | if (is_undef(from)) { |
304 | fail_expr(loop->from.expr); |
305 | instantiation_error = loop; |
306 | return 0; |
307 | } |
308 | if (!is_dimensionless(from)) { |
309 | fail("incompatible type for start value"); |
310 | fail_expr(loop->from.expr); |
311 | instantiation_error = loop; |
312 | return 0; |
313 | } |
314 | |
315 | to = eval_num(loop->to.expr, frame); |
316 | if (is_undef(to)) { |
317 | fail_expr(loop->to.expr); |
318 | instantiation_error = loop; |
319 | return 0; |
320 | } |
321 | if (!is_dimensionless(to)) { |
322 | fail("incompatible type for end value"); |
323 | fail_expr(loop->to.expr); |
324 | instantiation_error = loop; |
325 | return 0; |
326 | } |
327 | |
328 | assert(!loop->initialized); |
329 | loop->curr_value = from.n; |
330 | loop->initialized = 1; |
331 | |
332 | n = 0; |
333 | for (; loop->curr_value <= to.n; loop->curr_value += 1) { |
334 | if (n >= MAX_ITERATIONS) { |
335 | fail("%s: too many iterations (%d)", loop->var.name, |
336 | MAX_ITERATIONS); |
337 | instantiation_error = loop; |
338 | goto fail; |
339 | } |
340 | found_before = found; |
341 | if (loop->found == loop->active) |
342 | suspend_search(); |
343 | ok = run_loops(frame, loop->next, base, |
344 | active && loop->active == n); |
345 | if (loop->found == loop->active) |
346 | resume_search(); |
347 | if (!ok) |
348 | goto fail; |
349 | if (found_before != found) |
350 | loop->found = n; |
351 | n++; |
352 | } |
353 | loop->initialized = 0; |
354 | loop->curr_value = UNDEF; |
355 | if (active) { |
356 | loop->n = from.n; |
357 | loop->iterations = n; |
358 | } |
359 | return 1; |
360 | |
361 | fail: |
362 | loop->initialized = 0; |
363 | return 0; |
364 | } |
365 | |
366 | |
367 | static int iterate_tables(struct frame *frame, struct table *table, |
368 | struct coord base, int active) |
369 | { |
370 | int found_before, ok; |
371 | |
372 | if (!table) |
373 | return run_loops(frame, frame->loops, base, active); |
374 | for (table->curr_row = table->rows; table->curr_row; |
375 | table->curr_row = table->curr_row->next) { |
376 | found_before = found; |
377 | if (table->found_row == table->active_row) |
378 | suspend_search(); |
379 | ok = iterate_tables(frame, table->next, base, |
380 | active && table->active_row == table->curr_row); |
381 | if (table->found_row == table->active_row) |
382 | resume_search(); |
383 | if (!ok) |
384 | return 0; |
385 | if (found_before != found) |
386 | table->found_row = table->curr_row; |
387 | } |
388 | return 1; |
389 | } |
390 | |
391 | |
392 | static int generate_frame(struct frame *frame, struct coord base, |
393 | const struct frame *parent, struct obj *frame_ref, int active) |
394 | { |
395 | int ok; |
396 | |
397 | /* |
398 | * We ensure during construction that frames can never recurse. |
399 | */ |
400 | inst_begin_frame(frame_ref, frame, base, |
401 | active && parent == active_frame, |
402 | active && frame == active_frame); |
403 | frame->curr_parent = parent; |
404 | ok = iterate_tables(frame, frame->tables, base, active); |
405 | inst_end_frame(frame); |
406 | frame->curr_parent = NULL; |
407 | return ok; |
408 | } |
409 | |
410 | |
411 | static void reset_all_loops(void) |
412 | { |
413 | const struct frame *frame; |
414 | struct loop *loop; |
415 | |
416 | for (frame = frames; frame; frame = frame->next) |
417 | for (loop = frame->loops; loop; loop = loop->next) |
418 | loop->iterations = 0; |
419 | } |
420 | |
421 | |
422 | static void reset_found(void) |
423 | { |
424 | struct frame *frame; |
425 | struct table *table; |
426 | struct loop *loop; |
427 | |
428 | for (frame = frames; frame; frame = frame->next) { |
429 | for (table = frame->tables; table; table = table->next) |
430 | table->found_row = NULL; |
431 | for (loop = frame->loops; loop; loop = loop->next) |
432 | loop->found = -1; |
433 | frame->found_ref = NULL; |
434 | } |
435 | } |
436 | |
437 | |
438 | /* |
439 | * Note: we don't use frame->found_ref yet. Instead, we adjust the frame |
440 | * references with activate_item in inst.c |
441 | */ |
442 | |
443 | static void activate_found(void) |
444 | { |
445 | struct frame *frame; |
446 | struct table *table; |
447 | struct loop *loop; |
448 | |
449 | for (frame = frames; frame; frame = frame->next) { |
450 | for (table = frame->tables; table; table = table->next) |
451 | if (table->found_row) |
452 | table->active_row = table->found_row; |
453 | for (loop = frame->loops; loop; loop = loop->next) |
454 | if (loop->found != -1) |
455 | loop->active = loop->found; |
456 | if (frame->found_ref) |
457 | frame->active_ref = frame->found_ref; |
458 | } |
459 | } |
460 | |
461 | |
462 | int instantiate(void) |
463 | { |
464 | struct coord zero = { 0, 0 }; |
465 | int ok; |
466 | |
467 | meas_start(); |
468 | inst_start(); |
469 | instantiation_error = NULL; |
470 | reset_all_loops(); |
471 | reset_found(); |
472 | found = 0; |
473 | search_suspended = 0; |
474 | ok = generate_frame(root_frame, zero, NULL, NULL, 1); |
475 | if (ok && (find_vec || find_obj) && found) |
476 | activate_found(); |
477 | find_vec = NULL; |
478 | find_obj = NULL; |
479 | if (ok) |
480 | ok = link_holes(); |
481 | if (ok) |
482 | ok = refine_layers(); |
483 | if (ok) |
484 | ok = instantiate_meas(); |
485 | if (ok) |
486 | inst_commit(); |
487 | else |
488 | inst_revert(); |
489 | return ok; |
490 | } |
491 | |
492 | |
493 | /* ----- deallocation ------------------------------------------------------ */ |
494 | |
495 | |
496 | void obj_cleanup(void) |
497 | { |
498 | free(pkg_name); |
499 | while (frames) { |
500 | delete_frame(frames); |
501 | destroy(); |
502 | } |
503 | } |
504 |
Branches:
master