1/**
2 * @file arrange_profiles.cpp
3 * Classify and process a list of candidate sample files
4 * into merged sets and classes.
5 *
6 * @remark Copyright 2003 OProfile authors
7 * @remark Read the file COPYING
8 *
9 * @author John Levon
10 */
11
12#include <algorithm>
13#include <cstdlib>
14#include <iostream>
15#include <iterator>
16#include <map>
17#include <set>
18
19#include "string_manip.h"
20#include "op_header.h"
21#include "op_exception.h"
22
23#include "arrange_profiles.h"
24#include "format_output.h"
25#include "xml_utils.h"
26#include "parse_filename.h"
27#include "locate_images.h"
28
29using namespace std;
30
31namespace {
32
33int numeric_compare(string const & lhs, string const & rhs)
34{
35	if (lhs == "all" && rhs == "all")
36		return 0;
37	// we choose an order arbitrarily
38	if (lhs == "all")
39		return 1;
40	if (rhs == "all")
41		return -1;
42	unsigned int lhsval = op_lexical_cast<unsigned int>(lhs);
43	unsigned int rhsval = op_lexical_cast<unsigned int>(rhs);
44	if (lhsval == rhsval)
45		return 0;
46	if (lhsval < rhsval)
47		return -1;
48	return 1;
49}
50
51
52} // anonymous namespace
53
54
55// global to fix some C++ obscure corner case.
56bool operator<(profile_class const & lhs,
57               profile_class const & rhs)
58{
59	profile_template const & lt = lhs.ptemplate;
60	profile_template const & rt = rhs.ptemplate;
61	int comp;
62
63	// The profile classes are used to traverse the sample data
64	// arrays.  We create XML elements for <process> and <thread>
65	// that contain the sample data that can then be divided amongst
66	// CPU, event, mask axes so it is more convenient to have the
67	// process and thread classes be the outermost nesting level of
68	// the sample data arrays
69	if (!want_xml) {
70		comp = numeric_compare(lt.cpu, rt.cpu);
71		if (comp)
72			return comp < 0;
73	}
74
75	comp = numeric_compare(lt.tgid, rt.tgid);
76	if (comp)
77		return comp < 0;
78
79	comp = numeric_compare(lt.tid, rt.tid);
80	if (comp)
81		return comp < 0;
82
83	comp = numeric_compare(lt.unitmask, rt.unitmask);
84	if (comp)
85		return comp < 0;
86
87	if (want_xml) {
88		if (lt.event != rt.event)
89			return lt.event < rt.event;
90		if (lt.count != rt.count)
91			return lt.count < rt.count;
92
93		return numeric_compare(lt.cpu, rt.cpu) < 0;
94	} else {
95		if (lt.event == rt.event)
96			return lt.count < rt.count;
97		return lt.event < rt.event;
98	}
99}
100
101namespace {
102
103struct axis_t {
104	string name;
105	string suggestion;
106} axes[AXIS_MAX] = {
107	{ "event", "specify event:, count: or unitmask: (see also --merge=unitmask)" },
108	{ "tgid", "specify tgid: or --merge tgid" },
109	{ "tid", "specify tid: or --merge tid" },
110	{ "cpu", "specify cpu: or --merge cpu" },
111};
112
113} // anonymous namespace
114
115
116bool profile_classes::matches(profile_classes const & classes)
117{
118	if (v.size() != classes.v.size())
119		return false;
120
121	axis_types const axis2 = classes.axis;
122
123	switch (axis) {
124		case AXIS_EVENT:
125			break;
126		case AXIS_TGID:
127		case AXIS_TID:
128			return axis2 == AXIS_TID || axis2 == AXIS_TGID;
129		case AXIS_CPU:
130			return axis2 == AXIS_CPU;
131		case AXIS_MAX:
132			return false;
133	}
134
135	// check that the events match (same event, count)
136
137	vector<profile_class>::const_iterator it1 = v.begin();
138	vector<profile_class>::const_iterator end1 = v.end();
139	vector<profile_class>::const_iterator it2 = classes.v.begin();
140
141	while (it1 != end1) {
142		if (it1->ptemplate.event != it2->ptemplate.event)
143			return false;
144		if (it1->ptemplate.count != it2->ptemplate.count)
145			return false;
146		// differing unit mask is considered comparable
147		++it1;
148		++it2;
149	}
150
151	return true;
152}
153
154namespace {
155
156typedef growable_vector<string> event_array_t;
157typedef growable_vector<string>::size_type event_index_t;
158
159bool new_event_index(string event, event_array_t & events, event_index_t & index)
160{
161	event_index_t sz = events.size();
162	for (event_index_t i = 0; i != sz; ++i) {
163		if (events[i] == event) {
164			index = i;
165			return false;
166		}
167	}
168
169	index = sz;
170	events[sz] = event;
171	return true;
172}
173
174
175/// We have more than one axis of classification, tell the user.
176void report_error(profile_classes const & classes, axis_types newaxis)
177{
178	string str = "Already displaying results for parameter ";
179	str += axes[classes.axis].name;
180	str += " with values:\n";
181	vector<profile_class>::const_iterator it = classes.v.begin();
182	vector<profile_class>::const_iterator const end = classes.v.end();
183
184	// We show error for the first conflicting axis but on this
185	// axis we can get only a few different it->name, we display only
186	// these different name.
187	set <string> name_seen;
188	size_t i = 5;
189	for (; it != end && i; ++it) {
190		if (name_seen.find(it->name) == name_seen.end()) {
191			name_seen.insert(it->name);
192			str += it->name + ",";
193			--i;
194		}
195	}
196
197	if (!i) {
198		str += " and ";
199		str += op_lexical_cast<string>(classes.v.size() - 5);
200		str += " more,";
201	}
202
203	str += "\nwhich conflicts with parameter ";
204	str += axes[newaxis].name += ".\n";
205	str += "Suggestion: ";
206	str += axes[classes.axis].suggestion;
207	throw op_fatal_error(str);
208}
209
210
211/**
212 * check that two different axes are OK - this is only
213 * allowed if they are TGID,TID and for each class,
214 * tid == tgid
215 */
216bool allow_axes(profile_classes const & classes, axis_types newaxis)
217{
218	// No previous axis - OK
219	if (classes.axis == AXIS_MAX)
220		return true;
221
222	if (classes.axis != AXIS_TID && classes.axis != AXIS_TGID)
223		return false;
224
225	if (newaxis != AXIS_TID && newaxis != AXIS_TGID)
226		return false;
227
228	vector<profile_class>::const_iterator it = classes.v.begin();
229	vector<profile_class>::const_iterator const end = classes.v.end();
230
231	for (; it != end; ++it) {
232		if (it->ptemplate.tgid != it->ptemplate.tid)
233			return false;
234	}
235
236	return true;
237}
238
239
240/// find the first sample file header in the class
241opd_header const get_first_header(profile_class const & pclass)
242{
243	profile_set const & profile = *(pclass.profiles.begin());
244
245	string file;
246
247	// could be only one main app, with no samples for the main image
248	if (profile.files.empty()) {
249		profile_dep_set const & dep = *(profile.deps.begin());
250		list<profile_sample_files> const & files = dep.files;
251		profile_sample_files const & sample_files = *(files.begin());
252		if (!sample_files.sample_filename.empty())
253			file = sample_files.sample_filename;
254		else
255			file = *sample_files.cg_files.begin();
256	} else {
257		profile_sample_files const & sample_files
258			= *(profile.files.begin());
259		if (!sample_files.sample_filename.empty())
260			file = sample_files.sample_filename;
261		else
262			file = *sample_files.cg_files.begin();
263	}
264
265	return read_header(file);
266}
267
268/// merge sample file header in the profile_sample_files
269void merge_header(profile_sample_files const & files, opd_header & header)
270{
271	if (!files.sample_filename.empty()) {
272		opd_header const temp = read_header(files.sample_filename);
273		header.ctr_um |=  temp.ctr_um;
274	}
275
276	list<string>::const_iterator it = files.cg_files.begin();
277	list<string>::const_iterator const end = files.cg_files.end();
278	for ( ; it != end; ++it) {
279		opd_header const temp = read_header(*it);
280		header.ctr_um |= temp.ctr_um;
281	}
282}
283
284/// merge sample file header in the class
285opd_header const get_header(profile_class const & pclass,
286                            merge_option const & merge_by)
287{
288	opd_header header = get_first_header(pclass);
289
290	if (!merge_by.unitmask)
291		return header;
292
293	profile_set const & profile = *(pclass.profiles.begin());
294
295	typedef list<profile_sample_files>::const_iterator citerator;
296
297	citerator it = profile.files.begin();
298	citerator const end = profile.files.end();
299	for ( ; it != end; ++it)
300		merge_header(*it, header);
301
302	list<profile_dep_set>::const_iterator dep_it = profile.deps.begin();
303	list<profile_dep_set>::const_iterator dep_end = profile.deps.end();
304	for ( ; dep_it != dep_end; ++dep_it) {
305		citerator it = dep_it->files.begin();
306		citerator const end = dep_it->files.end();
307		for ( ; it != end; ++it)
308			merge_header(*it, header);
309	}
310
311	return header;
312}
313
314
315/// Give human-readable names to each class.
316void name_classes(profile_classes & classes, merge_option const & merge_by)
317{
318	opd_header header = get_header(classes.v[0], merge_by);
319
320	classes.event = describe_header(header);
321	classes.cpuinfo = describe_cpu(header);
322
323	// If we're splitting on event anyway, clear out the
324	// global event name
325	if (classes.axis == AXIS_EVENT)
326		classes.event.erase();
327
328	vector<profile_class>::iterator it = classes.v.begin();
329	vector<profile_class>::iterator const end = classes.v.end();
330
331	for (; it != end; ++it) {
332		it->name = axes[classes.axis].name + ":";
333		switch (classes.axis) {
334		case AXIS_EVENT:
335			it->name = it->ptemplate.event
336				+ ":" + it->ptemplate.count;
337			header = get_header(*it, merge_by);
338			it->longname = describe_header(header);
339			break;
340		case AXIS_TGID:
341			it->name += it->ptemplate.tgid;
342			it->longname = "Processes with a thread group ID of ";
343			it->longname += it->ptemplate.tgid;
344			break;
345		case AXIS_TID:
346			it->name += it->ptemplate.tid;
347			it->longname = "Processes with a thread ID of ";
348			it->longname += it->ptemplate.tid;
349			break;
350		case AXIS_CPU:
351			it->name += it->ptemplate.cpu;
352			it->longname = "Samples on CPU " + it->ptemplate.cpu;
353			break;
354		case AXIS_MAX:;
355		}
356	}
357}
358
359
360/**
361 * Name and verify classes.
362 */
363void identify_classes(profile_classes & classes,
364                      merge_option const & merge_by)
365{
366	profile_template & ptemplate = classes.v[0].ptemplate;
367	bool changed[AXIS_MAX] = { false, };
368
369	vector<profile_class>::iterator it = classes.v.begin();
370	++it;
371	vector<profile_class>::iterator end = classes.v.end();
372
373	// only one class, name it after the event
374	if (it == end)
375		changed[AXIS_EVENT] = true;
376
377	for (; it != end; ++it) {
378		if (it->ptemplate.event != ptemplate.event
379		    ||  it->ptemplate.count != ptemplate.count
380		    // unit mask are mergeable
381		    || (!merge_by.unitmask
382			&& it->ptemplate.unitmask != ptemplate.unitmask))
383			changed[AXIS_EVENT] = true;
384
385		// we need the merge checks here because each
386		// template is filled in from the first non
387		// matching profile, so just because they differ
388		// doesn't mean it's the axis we care about
389		if (!merge_by.tgid && it->ptemplate.tgid != ptemplate.tgid)
390			changed[AXIS_TGID] = true;
391
392		if (!merge_by.tid && it->ptemplate.tid != ptemplate.tid)
393			changed[AXIS_TID] = true;
394
395		if (!merge_by.cpu && it->ptemplate.cpu != ptemplate.cpu)
396			changed[AXIS_CPU] = true;
397	}
398
399	classes.axis = AXIS_MAX;
400
401	for (size_t i = 0; i < AXIS_MAX; ++i) {
402		if (!changed[i])
403			continue;
404
405		if (!allow_axes(classes, axis_types(i)))
406			report_error(classes, axis_types(i));
407		classes.axis = axis_types(i);
408		/* do this early for report_error */
409		name_classes(classes, merge_by);
410	}
411
412	if (classes.axis == AXIS_MAX) {
413		cerr << "Internal error - no equivalence class axis" << endl;
414		abort();
415	}
416}
417
418void identify_xml_classes(profile_classes & classes, merge_option const & merge_by)
419{
420	opd_header header = get_header(classes.v[0], merge_by);
421
422	vector<profile_class>::iterator it = classes.v.begin();
423	vector<profile_class>::iterator end = classes.v.end();
424
425	event_index_t event_num;
426	event_index_t event_max = 0;
427	event_array_t event_array;
428	size_t nr_cpus = 0;
429	bool has_nonzero_mask = false;
430
431	ostringstream event_setup;
432
433	// fill in XML identifying each event, and replace event name by event_num
434	for (; it != end; ++it) {
435		string mask = it->ptemplate.unitmask;
436		if (mask.find_first_of("x123456789abcdefABCDEF") != string::npos)
437			has_nonzero_mask = true;
438		if (new_event_index(it->ptemplate.event, event_array, event_num)) {
439			// replace it->ptemplate.event with the event_num string
440			// this is the first time we've seen this event
441			header = get_header(*it, merge_by);
442			event_setup << describe_header(header);
443			event_max = event_num;
444		}
445		if (it->ptemplate.cpu != "all") {
446			size_t cpu = atoi(it->ptemplate.cpu.c_str());
447			if (cpu > nr_cpus) nr_cpus = cpu;
448		}
449
450		ostringstream str;
451		str << event_num;
452		it->ptemplate.event = str.str();
453	}
454	xml_utils::set_nr_cpus(++nr_cpus);
455	xml_utils::set_nr_events(event_max+1);
456	if (has_nonzero_mask)
457		xml_utils::set_has_nonzero_masks();
458	classes.event = event_setup.str();
459	classes.cpuinfo = describe_cpu(header);
460}
461
462/// construct a class template from a profile
463profile_template const
464template_from_profile(parsed_filename const & parsed,
465                      merge_option const & merge_by)
466{
467	profile_template ptemplate;
468
469	ptemplate.event = parsed.event;
470	ptemplate.count = parsed.count;
471
472	if (!merge_by.unitmask)
473		ptemplate.unitmask = parsed.unitmask;
474	if (!merge_by.tgid)
475		ptemplate.tgid = parsed.tgid;
476	if (!merge_by.tid)
477		ptemplate.tid = parsed.tid;
478	if (!merge_by.cpu)
479		ptemplate.cpu = parsed.cpu;
480	return ptemplate;
481}
482
483
484/**
485 * Find a matching class the sample file could go in, or generate
486 * a new class if needed.
487 * This is the heart of the merging and classification process.
488 * The returned value is non-const reference but the ptemplate member
489 * must be considered as const
490 */
491profile_class & find_class(set<profile_class> & classes,
492                           parsed_filename const & parsed,
493                           merge_option const & merge_by)
494{
495	profile_class cls;
496	cls.ptemplate = template_from_profile(parsed, merge_by);
497
498	pair<set<profile_class>::iterator, bool> ret = classes.insert(cls);
499
500	return const_cast<profile_class &>(*ret.first);
501}
502
503/**
504 * Sanity check : we can't overwrite sample_filename, if we abort here it means
505 * we fail to detect that parsed sample filename for two distinct samples
506 * filename must go in two distinct profile_sample_files. This assumption is
507 * false for callgraph samples files so this function is only called for non cg
508 * files.
509 */
510void sanitize_profile_sample_files(profile_sample_files const & sample_files,
511    parsed_filename const & parsed)
512{
513	// We can't allow to overwrite sample_filename.
514	if (!sample_files.sample_filename.empty()) {
515		ostringstream out;
516		out << "sanitize_profile_sample_files(): sample file "
517		    << "parsed twice ?\nsample_filename:\n"
518		    << sample_files.sample_filename << endl
519		    << parsed << endl;
520		throw op_fatal_error(out.str());
521	}
522}
523
524
525/**
526 * Add a sample filename (either cg or non cg files) to this profile.
527 */
528void
529add_to_profile_sample_files(profile_sample_files & sample_files,
530    parsed_filename const & parsed)
531{
532	if (parsed.cg_image.empty()) {
533		// We can't allow to overwrite sample_filename.
534		sanitize_profile_sample_files(sample_files, parsed);
535
536		sample_files.sample_filename = parsed.filename;
537	} else {
538		sample_files.cg_files.push_back(parsed.filename);
539	}
540}
541
542
543/**
544 * we need to fix cg filename: a callgraph filename can occur before the binary
545 * non callgraph samples filename occur so we must search.
546 */
547profile_sample_files &
548find_profile_sample_files(list<profile_sample_files> & files,
549			  parsed_filename const & parsed,
550			  extra_images const & extra)
551{
552	list<profile_sample_files>::iterator it;
553	list<profile_sample_files>::iterator const end = files.end();
554	for (it = files.begin(); it != end; ++it) {
555		if (!it->sample_filename.empty()) {
556			parsed_filename psample_filename =
557			  parse_filename(it->sample_filename, extra);
558			if (psample_filename.lib_image == parsed.lib_image &&
559			    psample_filename.image == parsed.image &&
560			    psample_filename.profile_spec_equal(parsed))
561				return *it;
562		}
563
564		list<string>::const_iterator cit;
565		list<string>::const_iterator const cend = it->cg_files.end();
566		for (cit = it->cg_files.begin(); cit != cend; ++cit) {
567			parsed_filename pcg_filename =
568				parse_filename(*cit, extra);
569			if (pcg_filename.lib_image == parsed.lib_image &&
570			    pcg_filename.image == parsed.image &&
571			    pcg_filename.profile_spec_equal(parsed))
572				return *it;
573		}
574	}
575
576	// not found, create a new one
577	files.push_back(profile_sample_files());
578	return files.back();
579}
580
581
582/**
583 * Add a profile to particular profile set. If the new profile is
584 * a dependent image, it gets added to the dep list, or just placed
585 * on the normal list of profiles otherwise.
586 */
587void
588add_to_profile_set(profile_set & set, parsed_filename const & parsed,
589		   bool merge_by_lib, extra_images const & extra)
590{
591	if (parsed.image == parsed.lib_image && !merge_by_lib) {
592		profile_sample_files & sample_files =
593			find_profile_sample_files(set.files, parsed, extra);
594		add_to_profile_sample_files(sample_files, parsed);
595		return;
596	}
597
598	list<profile_dep_set>::iterator it = set.deps.begin();
599	list<profile_dep_set>::iterator const end = set.deps.end();
600
601	for (; it != end; ++it) {
602		if (it->lib_image == parsed.lib_image && !merge_by_lib &&
603				parsed.jit_dumpfile_exists == false) {
604			profile_sample_files & sample_files =
605				find_profile_sample_files(it->files, parsed,
606							  extra);
607			add_to_profile_sample_files(sample_files, parsed);
608			return;
609		}
610	}
611
612	profile_dep_set depset;
613	depset.lib_image = parsed.lib_image;
614	profile_sample_files & sample_files =
615		find_profile_sample_files(depset.files, parsed, extra);
616	add_to_profile_sample_files(sample_files, parsed);
617	set.deps.push_back(depset);
618}
619
620
621/**
622 * Add a profile to a particular equivalence class. The previous matching
623 * will have ensured the profile "fits", so now it's just a matter of
624 * finding which sample file list it needs to go on.
625 */
626void add_profile(profile_class & pclass, parsed_filename const & parsed,
627		 bool merge_by_lib, extra_images const & extra)
628{
629	list<profile_set>::iterator it = pclass.profiles.begin();
630	list<profile_set>::iterator const end = pclass.profiles.end();
631
632	for (; it != end; ++it) {
633		if (it->image == parsed.image) {
634			add_to_profile_set(*it, parsed, merge_by_lib, extra);
635			return;
636		}
637	}
638
639	profile_set set;
640	set.image = parsed.image;
641	add_to_profile_set(set, parsed, merge_by_lib, extra);
642	pclass.profiles.push_back(set);
643}
644
645}  // anon namespace
646
647
648profile_classes const
649arrange_profiles(list<string> const & files, merge_option const & merge_by,
650		 extra_images const & extra)
651{
652	set<profile_class> temp_classes;
653
654	list<string>::const_iterator it = files.begin();
655	list<string>::const_iterator const end = files.end();
656
657	for (; it != end; ++it) {
658		parsed_filename parsed = parse_filename(*it, extra);
659
660		if (parsed.lib_image.empty())
661			parsed.lib_image = parsed.image;
662
663		// This simplifies the add of the profile later,
664		// if we're lib-merging, then the app_image cannot
665		// matter. After this, any non-dependent has
666		// image == lib_image
667		if (merge_by.lib)
668			parsed.image = parsed.lib_image;
669
670		profile_class & pclass =
671			find_class(temp_classes, parsed, merge_by);
672		add_profile(pclass, parsed, merge_by.lib, extra);
673	}
674
675	profile_classes classes;
676	copy(temp_classes.begin(), temp_classes.end(),
677	     back_inserter(classes.v));
678
679	if (classes.v.empty())
680		return classes;
681
682	// sort by template for nicely ordered columns
683	stable_sort(classes.v.begin(), classes.v.end());
684
685	if (want_xml)
686		identify_xml_classes(classes, merge_by);
687	else
688		identify_classes(classes, merge_by);
689
690	classes.extra_found_images = extra;
691
692	return classes;
693}
694
695
696ostream & operator<<(ostream & out, profile_sample_files const & sample_files)
697{
698	out << "sample_filename: " << sample_files.sample_filename << endl;
699	out << "callgraph filenames:\n";
700	copy(sample_files.cg_files.begin(), sample_files.cg_files.end(),
701	     ostream_iterator<string>(out, "\n"));
702	return out;
703}
704
705ostream & operator<<(ostream & out, profile_dep_set const & pdep_set)
706{
707	out << "lib_image: " << pdep_set.lib_image << endl;
708
709	list<profile_sample_files>::const_iterator it;
710	list<profile_sample_files>::const_iterator const end =
711		pdep_set.files.end();
712	size_t i = 0;
713	for (it = pdep_set.files.begin(); it != end; ++it)
714		out << "profile_sample_files #" << i++ << ":\n" << *it;
715
716	return out;
717}
718
719ostream & operator<<(ostream & out, profile_set const & pset)
720{
721	out << "image: " << pset.image << endl;
722
723	list<profile_sample_files>::const_iterator it;
724	list<profile_sample_files>::const_iterator const end =
725		pset.files.end();
726	size_t i = 0;
727	for (it = pset.files.begin(); it != end; ++it)
728		out << "profile_sample_files #" << i++ << ":\n" << *it;
729
730	list<profile_dep_set>::const_iterator cit;
731	list<profile_dep_set>::const_iterator const cend = pset.deps.end();
732	i = 0;
733	for (cit = pset.deps.begin(); cit != cend; ++cit)
734		out << "profile_dep_set #" << i++ << ":\n" << *cit;
735
736	return out;
737}
738
739ostream & operator<<(ostream & out, profile_template const & ptemplate)
740{
741	out << "event: " << ptemplate.event << endl
742	    << "count: " << ptemplate.count << endl
743	    << "unitmask: " << ptemplate.unitmask << endl
744	    << "tgid: " << ptemplate.tgid << endl
745	    << "tid: " << ptemplate.tid << endl
746	    << "cpu: " << ptemplate.cpu << endl;
747	return out;
748}
749
750ostream & operator<<(ostream & out, profile_class const & pclass)
751{
752	out << "name: " << pclass.name << endl
753	    << "longname: " << pclass.longname << endl
754	    << "ptemplate:\n" << pclass.ptemplate;
755
756	size_t i = 0;
757	list<profile_set>::const_iterator it;
758	list<profile_set>::const_iterator const end = pclass.profiles.end();
759	for (it = pclass.profiles.begin(); it != end; ++it)
760		out << "profiles_set #" << i++ << ":\n" << *it;
761
762	return out;
763}
764
765ostream & operator<<(ostream & out, profile_classes const & pclasses)
766{
767	out << "event: " << pclasses.event << endl
768	    << "cpuinfo: " << pclasses.cpuinfo << endl;
769
770	for (size_t i = 0; i < pclasses.v.size(); ++i)
771		out << "class #" << i << ":\n" << pclasses.v[i];
772
773	return out;
774}
775
776
777namespace {
778
779/// add the files to group of image sets
780void add_to_group(image_group_set & group, string const & app_image,
781                  list<profile_sample_files> const & files)
782{
783	image_set set;
784	set.app_image = app_image;
785	set.files = files;
786	group.push_back(set);
787}
788
789
790typedef map<string, inverted_profile> app_map_t;
791
792
793inverted_profile &
794get_iprofile(app_map_t & app_map, string const & image, size_t nr_classes)
795{
796	app_map_t::iterator ait = app_map.find(image);
797	if (ait != app_map.end())
798		return ait->second;
799
800	inverted_profile ip;
801	ip.image = image;
802	ip.groups.resize(nr_classes);
803	app_map[image] = ip;
804	return app_map[image];
805}
806
807
808/// Pull out all the images, removing any we can't access.
809void
810verify_and_fill(app_map_t & app_map, list<inverted_profile> & plist,
811		extra_images const & extra)
812{
813	app_map_t::iterator it = app_map.begin();
814	app_map_t::iterator const end = app_map.end();
815
816	for (; it != end; ++it) {
817		plist.push_back(it->second);
818		inverted_profile & ip = plist.back();
819		extra.find_image_path(ip.image, ip.error, false);
820	}
821}
822
823} // anon namespace
824
825
826list<inverted_profile> const
827invert_profiles(profile_classes const & classes)
828{
829	app_map_t app_map;
830
831	size_t nr_classes = classes.v.size();
832
833	for (size_t i = 0; i < nr_classes; ++i) {
834		list<profile_set>::const_iterator pit
835			= classes.v[i].profiles.begin();
836		list<profile_set>::const_iterator pend
837			= classes.v[i].profiles.end();
838
839		for (; pit != pend; ++pit) {
840			// files can be empty if samples for a lib image
841			// but none for the main image. Deal with it here
842			// rather than later.
843			if (pit->files.size()) {
844				inverted_profile & ip = get_iprofile(app_map,
845					pit->image, nr_classes);
846				add_to_group(ip.groups[i], pit->image, pit->files);
847			}
848
849			list<profile_dep_set>::const_iterator dit
850				= pit->deps.begin();
851			list<profile_dep_set>::const_iterator const dend
852				= pit->deps.end();
853
854			for (;  dit != dend; ++dit) {
855				inverted_profile & ip = get_iprofile(app_map,
856					dit->lib_image, nr_classes);
857				add_to_group(ip.groups[i], pit->image,
858				             dit->files);
859			}
860		}
861	}
862
863	list<inverted_profile> inverted_list;
864
865	verify_and_fill(app_map, inverted_list, classes.extra_found_images);
866
867	return inverted_list;
868}
869